#include<iostream>
#include<cstring>
#include<cstdio>
#define M 100005
#define ld long double
int head[M],next[*M],u[*M],l[*M],n,m,cnt,du[M],v[M],root,now,fa[M],c[M];
ld d[M],f[M],g[M],gg[M];
using namespace std;
void jia(int a1,int a2,int a3)
{
cnt++;
u[cnt]=a2;
l[cnt]=a3;
next[cnt]=head[a1];
head[a1]=cnt;
return;
}
void dfs1(int a1)
{
v[a1]=;
for(int i=head[a1];i;i=next[i])
if(!v[u[i]]&&!c[u[i]])
{
dfs1(u[i]);
du[a1]++;
d[a1]+=f[u[i]]+(ld)l[i];
}
if(du[a1])
f[a1]=d[a1]/(ld)du[a1];
if(a1!=root)
du[a1]++;
return;
}
void dfs2(int a1)
{
v[a1]=;
for(int i=head[a1];i;i=next[i])
if(!v[u[i]]&&!c[u[i]])
{
int k=du[a1]-;
if(!k)
k++;
d[u[i]]+=(d[a1]-f[u[i]]-(ld)l[i])/(ld)k+(ld)l[i];
dfs2(u[i]);
}
return;
}
void zhao(int a1)
{
v[a1]=++now;
for(int i=head[a1];i;i=next[i])
if(!v[u[i]])
{
fa[u[i]]=a1;
zhao(u[i]);
}
else if(u[i]!=fa[a1]&&v[a1]>v[u[i]])
{
c[u[i]]=;
for(;a1!=u[i];)
{
c[a1]=;
a1=fa[a1];
}
}
return;
}
void huan(int a1,int fa)
{
bool kg=;
g[a1]=0.00000;
for(int i=head[a1];i;i=next[i])
if(c[u[i]]&&u[i]!=fa&&u[i]!=root)
{
kg=;
huan(u[i],a1);
g[a1]+=g[u[i]]+(ld)l[i];
}
if(a1==root)
return;
int k=du[a1];
if(!k)
k++;
if(kg)
g[a1]=d[a1]/(ld)k;
else
{
k=du[a1]+;
g[a1]=(g[a1]+d[a1])/(ld)k;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int a1,a2,a3;
scanf("%d%d%d",&a1,&a2,&a3);
jia(a1,a2,a3);
jia(a2,a1,a3);
}
if(n==m+)
{
root=;
dfs1();
for(int i=;i<=n;i++)
v[i]=;
dfs2();
}
else
{
zhao();
for(int i=;i<=n;i++)
v[i]=;
for(int i=;i<=n;i++)
if(c[i])
{
root=i;
dfs1(i);
}
for(int i=;i<=n;i++)
if(c[i])
{
root=i;
huan(i,);
gg[i]=g[i];
}
for(int i=;i<=n;i++)
if(c[i])
{
du[i]+=;
d[i]+=gg[i];
}
for(int i=;i<=n;i++)
v[i]=;
for(int i=;i<=n;i++)
if(c[i])
dfs2(i);
}
double ans=0.00000;
for(int i=;i<=n;i++)
ans+=d[i]/(ld)du[i];
printf("%.5lf\n",ans/(double)n);
return ;
}
基环树DP，先处理环外的子树，在递归处理环上的点。