原题地址这个算法是由本沙茶在现场使用的那个做法扩展得来的……其实AC不了，后两个点会因为常数过大而T掉……但在BZOJ上算总时间的话能AC……
首先考虑树的情形。设F[i]为从点i开始，往子树i里面走，到达叶结点的期望长度，则很容易得到递推公式：
F[i] = (ΣF[j] + W(i, j)) / K，其中j是i的子结点，K是i的子结点个数。
至于这个式子的证明……很容易搞的，就不说了囧。
这样，可以在O(N)时间内求出以树根为起点的期望长度。那么，以其它点为起点的期望长度如何得到？
我们定义一种“扭根”操作（类似平衡树中的旋转），可以把根结点的一个子结点“扭”到根上，并使根结点作为它的子结点（也就是把父子关系交换一下）。容易发现，每次“扭根”之后，只有原来的根结点和现在的根结点这两个结点的子结点发生了变化，因此，也只有这两个结点的F值可能发生变化，只需要重新求一下即可（其实不用重新求，只需要维护一个KS[]值表示某个结点的子结点个数，然后在维护的时候加上或减去相应项，并维护KS即可，这样可以确保每次维护的时间复杂度为O(1)）。注意“扭根”的顺序，需要按照DFS序，而且在遍历完一个结点回退的时候也要顺便“扭”回来。这样，就可以在O(N)的时间内得出以每个点为起点的期望长度，取它们的平均值即可。
然后考虑有环的情形，注意到，环上的结点数很少。由于只有一个环，所以先化为无向环套树形式。
设A为环上的一个结点。从A开始走，有可能走到它自己的树里，也有可能沿着环走到其它树里，但是，
A在环上的两条邻边不可能都走到。也就是，可以枚举是左邻边走不到还是右邻边走不到，并将这条边删除（反正走不到，要了不如不要），这样就变成了一棵树，对这棵树按照上面的算法求F值，即可求出以A为起点，
某一条邻边走不到情况下的期望长度。这里需要特别注意的是，在求F[A]时，最后除的那个数不是K，而是(K+1)，因为虽然这条邻边删掉了，但为了防止它走到还是要考虑一下的 。设F1[A]为A的左邻边走不到时的以A为起点的期望长度，F2[A]为A的右邻边走不到时的以A为起点的期望长度（本沙茶在代码里全用F1表示了囧），这其中有相同的部分，就是A的两条邻边都走不到时的期望长度，此时就是往A的树内走，按照树的求法求即可，注意求F[A]时除的是(K+2)，F1[A]+F2[A]再把这个相同的部分减掉，就是以A为起点的期望长度了。然后，采用“扭根”操作可以求出以A树中所有结点为起点的期望长度。枚举环上的所有结点，按照上述办法，就可以得到结果了。总时间复杂度为O(MN)，M为环上结点总数。
代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = 100010, INF = ~0U >> 2;
struct edge {
int a, b, w, pre, next;
bool mr;
} E0[(MAXN + 1) * 3], E[MAXN << 2];
int n, _n, m0, m, stk[MAXN], st[MAXN], pr[MAXN], pos_z, ts_len, TS[MAXN], Q[MAXN], pr1[MAXN], pr2[MAXN], lt[MAXN << 1], KS[MAXN];
bool loop_ex, vst[MAXN];
double F1[MAXN], F2[MAXN], res = 0;
void init_d0()
{
re(i, n) E0[i].pre = E0[i].next = i; if (n & 1) m0 = n + 1; else m0 = n;
}
void init_d()
{
re(i, n) E[i].pre = E[i].next = i; m = n;
}
void add_edge0(int a, int b, int w)
{
E0[m0].a = a; E0[m0].b = b; E0[m0].w = w; E0[m0].mr = 0; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
E0[m0].a = b; E0[m0].b = a; E0[m0].w = w; E0[m0].mr = 0; E0[m0].pre = E0[b].pre; E0[m0].next = b; E0[b].pre = m0; E0[E0[m0].pre].next = m0++;
}
void del_edge0(int No)
{
E0[E0[No].pre].next = E0[No].next; E0[E0[No].next].pre = E0[No].pre;
E0[E0[No ^ 1].pre].next = E0[No ^ 1].next; E0[E0[No ^ 1].next].pre = E0[No ^ 1].pre;
}
void resu_edge0(int No)
{
E0[E0[No].pre].next = E0[E0[No].next].pre = No;
E0[E0[No ^ 1].pre].next = E0[E0[No ^ 1].next].pre = No ^ 1;
}
void add_edge(int a, int b, int w, bool mr)
{
E[m].a = a; E[m].b = b; E[m].w = w; E[m].mr = mr; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
void del_edge(int No)
{
E[E[No].pre].next = E[No].next; E[E[No].next].pre = E[No].pre;
}
void resu_edge(int No)
{
E[E[No].pre].next = E[E[No].next].pre = No;
}
void init()
{
int m00, a0, b0, w0;
scanf("%d%d", &n, &m00); loop_ex = m00 == n; init_d0();
re(i, m00) {
scanf("%d%d%d", &a0, &b0, &w0);
add_edge0(--a0, --b0, w0);
}
}
void prepare()
{
re(i, n) {st[i] = E0[i].next; vst[i] = 0;}
int x, y, tp = 0; bool FF; stk[0] = 0; vst[0] = 1; pos_z = pr[0] = -1;
while (tp >= 0) {
x = stk[tp]; FF = 0;
for (int p=st[x]; p != x; p=E0[p].next) {
y = E0[p].b;
if (!vst[y]) {
vst[y] = FF = 1; stk[++tp] = y; pr[y] = p; st[x] = E0[p].next; break;
} else if (p != (pr[x] ^ 1) && pos_z == -1) pos_z = p;
}
if (!FF) tp--;
}
x = E0[pos_z].a; y = E0[pos_z].b; E0[pos_z].mr = E0[pos_z ^ 1].mr = 1; ts_len = 0;
while (x != y) {TS[ts_len++] = x; E0[pr[x]].mr = E0[pr[x] ^ 1].mr = 1; x = E0[pr[x]].a;} TS[ts_len++] = y;
}
void mkt(int z)
{
init_d(); re(j, n) vst[j] = 0;
int x, y; Q[0] = z; vst[z] = 1;
for (int front=0, rear=0; front<=rear; front++) {
x = Q[front];
for (int p=E0[x].next; p != x; p=E0[p].next) {
y = E0[p].b;
if (!vst[y]) {
vst[y] = 1; Q[++rear] = y; pr1[y] = m; add_edge(x, y, E0[p].w, E0[p].mr);
}
}
}
}
void mkt2(int z)
{
init_d(); re(j, n) vst[j] = 0;
int x, y, front, rear; Q[0] = z; vst[z] = 1;
for (front=0, rear=0; front<=rear; front++) {
x = Q[front];
for (int p=E0[x].next; p != x; p=E0[p].next) if (!E0[p].mr) {
y = E0[p].b;
if (!vst[y]) {
vst[y] = 1; Q[++rear] = y; pr1[y] = m; add_edge(x, y, E0[p].w, 0);
}
}
}
_n = rear + 1;
}
void solve()
{
int x, y, z, sum, tp, lt_len; bool FF;
if (loop_ex) {
prepare();
re(i, ts_len) {
x = TS[i];
if (i == ts_len - 1) del_edge0(pos_z); else del_edge0(pr[x]);
mkt(x);
rre(j, n) {
y = Q[j]; if (E[y].next == y) {F1[y] = 0; continue;}
if (y == x) sum = 1; else sum = 0; F1[y] = 0;
for (int p=E[y].next; p != y; p=E[p].next) {
z = E[p].b; F1[y] += F1[z] + E[p].w; sum++;
}
F1[y] /= sum; KS[y] = sum;
}
res += F1[x];
re(j, n) {st[j] = E[j].next; vst[j] = 0;} lt_len = 0; stk[tp = 0] = x;
while (tp >= 0) {
y = stk[tp]; FF = 0;
for (int p=st[y]; p != y; p=E[p].next) if (!E[p].mr) {
z = E[p].b;
if (!vst[z]) {
vst[z] = FF = 1; stk[++tp] = z; lt[lt_len++] = z; break;
}
}
if (!FF) {lt[lt_len++] = -y - 1; tp--;}
}
if (lt_len == 1) lt_len = 0;
re(j, lt_len) {
y = lt[j];
if (y >= 0) {
z = E[pr1[y]].a; del_edge(pr1[y]); pr2[z] = m; add_edge(y, z, E[pr1[y]].w, 0);
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]--; F1[z] -= E[pr1[y]].w + F1[y]; F1[z] /= KS[z];}
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]++; F1[y] += E[pr1[y]].w + F1[z]; F1[y] /= KS[y];}
res += F1[y];
} else {
y = -y - 1;
z = E[pr1[y]].a; del_edge(pr2[z]); resu_edge(pr1[y]);
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]--; F1[y] -= E[pr2[z]].w + F1[z]; F1[y] /= KS[y];}
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]++; F1[z] += E[pr2[z]].w + F1[y]; F1[z] /= KS[z];}
}
}
if (i == ts_len - 1) resu_edge0(pos_z); else resu_edge0(pr[x]);
if (!i) del_edge0(pos_z); else del_edge0(pr[TS[i - 1]]);
mkt(x);
rre(j, n) {
y = Q[j]; if (E[y].next == y) {F1[y] = 0; continue;}
if (y == x) sum = 1; else sum = 0; F1[y] = 0;
for (int p=E[y].next; p != y; p=E[p].next) {
z = E[p].b; F1[y] += F1[z] + E[p].w; sum++;
}
F1[y] /= sum; KS[y] = sum;
}
res += F1[x];
re(j, n) {st[j] = E[j].next; vst[j] = 0;} lt_len = 0; stk[tp = 0] = x;
while (tp >= 0) {
y = stk[tp]; FF = 0;
for (int p=st[y]; p != y; p=E[p].next) if (!E[p].mr) {
z = E[p].b;
if (!vst[z]) {
vst[z] = FF = 1; stk[++tp] = z; lt[lt_len++] = z; break;
}
}
if (!FF) {lt[lt_len++] = -y - 1; tp--;}
}
if (lt_len == 1) lt_len = 0;
re(j, lt_len) {
y = lt[j];
if (y >= 0) {
z = E[pr1[y]].a; del_edge(pr1[y]); pr2[z] = m; add_edge(y, z, E[pr1[y]].w, 0);
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]--; F1[z] -= E[pr1[y]].w + F1[y]; F1[z] /= KS[z];}
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]++; F1[y] += E[pr1[y]].w + F1[z]; F1[y] /= KS[y];}
res += F1[y];
} else {
y = -y - 1;
z = E[pr1[y]].a; del_edge(pr2[z]); resu_edge(pr1[y]);
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]--; F1[y] -= E[pr2[z]].w + F1[z]; F1[y] /= KS[y];}
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]++; F1[z] += E[pr2[z]].w + F1[y]; F1[z] /= KS[z];}
}
}
if (!i) resu_edge0(pos_z); else resu_edge0(pr[TS[i - 1]]);
mkt2(x);
rre(j, _n) {
y = Q[j]; if (E[y].next == y) {F1[y] = 0; continue;}
if (y == x) sum = 2; else sum = 0; F1[y] = 0;
for (int p=E[y].next; p != y; p=E[p].next) {
z = E[p].b; F1[y] += F1[z] + E[p].w; sum++;
}
F1[y] /= sum; KS[y] = sum;
}
res -= F1[x];
re(j, n) {st[j] = E[j].next; vst[j] = 0;} lt_len = 0; stk[tp = 0] = x;
while (tp >= 0) {
y = stk[tp]; FF = 0;
for (int p=st[y]; p != y; p=E[p].next) {
z = E[p].b;
if (!vst[z]) {
vst[z] = FF = 1; stk[++tp] = z; lt[lt_len++] = z; break;
}
}
if (!FF) {lt[lt_len++] = -y - 1; tp--;}
}
if (lt_len == 1) lt_len = 0;
re(j, lt_len) {
y = lt[j];
if (y >= 0) {
z = E[pr1[y]].a; del_edge(pr1[y]); pr2[z] = m; add_edge(y, z, E[pr1[y]].w, 0);
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]--; F1[z] -= E[pr1[y]].w + F1[y]; F1[z] /= KS[z];}
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]++; F1[y] += E[pr1[y]].w + F1[z]; F1[y] /= KS[y];}
res -= F1[y];
} else {
y = -y - 1;
z = E[pr1[y]].a; del_edge(pr2[z]); resu_edge(pr1[y]);
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]--; F1[y] -= E[pr2[z]].w + F1[z]; F1[y] /= KS[y];}
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]++; F1[z] += E[pr2[z]].w + F1[y]; F1[z] /= KS[z];}
}
}
}
} else {
mkt(0);
rre(i, n) {
y = Q[i]; if (E[y].next == y) {F1[y] = 0; continue;}
sum = 0; F1[y] = 0;
for (int p=E[y].next; p != y; p=E[p].next) {
z = E[p].b; F1[y] += F1[z] + E[p].w; sum++;
}
F1[y] /= sum; KS[y] = sum;
}
res += F1[0];
re(i, n) {st[i] = E[i].next; vst[i] = 0;} lt_len = 0; stk[tp = 0] = 0;
while (tp >= 0) {
y = stk[tp]; FF = 0;
for (int p=st[y]; p != y; p=E[p].next) if (!E[p].mr) {
z = E[p].b;
if (!vst[z]) {
vst[z] = FF = 1; stk[++tp] = z; lt[lt_len++] = z; break;
}
}
if (!FF) {lt[lt_len++] = -y - 1; tp--;}
}
re(i, lt_len) {
y = lt[i];
if (y >= 0) {
z = E[pr1[y]].a; del_edge(pr1[y]); pr2[z] = m; add_edge(y, z, E[pr1[y]].w, 0);
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]--; F1[z] -= E[pr1[y]].w + F1[y]; F1[z] /= KS[z];}
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]++; F1[y] += E[pr1[y]].w + F1[z]; F1[y] /= KS[y];}
res += F1[y];
} else {
y = -y - 1;
z = E[pr1[y]].a; del_edge(pr2[z]); resu_edge(pr1[y]);
if (E[y].next == y) {F1[y] = 0; KS[y] = 0;} else {F1[y] *= KS[y]--; F1[y] -= E[pr2[z]].w + F1[z]; F1[y] /= KS[y];}
if (E[z].next == z) {F1[z] = 0; KS[z] = 0;} else {F1[z] *= KS[z]++; F1[z] += E[pr2[z]].w + F1[y]; F1[z] /= KS[z];}
}
}
}
res /= n;
}
void pri()
{
printf("%.5lf\n", res);
}
int main()
{
init();
solve();
pri();
return 0;
}