1 /**************************************************************  2     Problem: 2878  3     User: zrts  4     Language: C++  5     Result: Accepted  6     Time:588 ms  7     Memory:10748 kb  8 ****************************************************************/  9   10 #include<iostream> 11 #include<cstdio> 12 #include<algorithm> 13 #include<cstring> 14 #include<vector> 15 //by zrt 16 //problem: 17 using namespace std; 18 typedef long long LL; 19 const int inf(0x3f3f3f3f); 20 const double eps(1e-9); 21 bool oncircle[100005]; 22 int du[100005]; 23 int fa[100005]; 24 int H[100005],X[200005],P[200005],tot; 25 double E[200005]; 26 inline void add(int x,int y,int z){//add an edge 27     P[++tot]=y;X[tot]=H[x];H[x]=tot;E[tot]=z; 28 } 29 int n,m; 30 double F[100005];//for son E 31 double D[100005];// F * |son| 32 double p[100005];// ans 33 int num[100005];// |son| 34 int pre[100005]; 35 double wpre[100005]; 36 bool type; 37 void treedp1(int x){//Dp the tree first 38     for(int i=H[x];i;i=X[i]){ 39         if(P[i]==fa[x]||oncircle[P[i]]) continue; 40         fa[P[i]]=x; 41         treedp1(P[i]); 42         D[x]+=F[P[i]]+E[i];num[x]++; 43     } 44     if(num[x]) 45     F[x]=D[x]/num[x]; 46     else F[x]=0; 47 } 48 void treedp2(int x,double edge){//Dp the tree second | calc the P 49     double other; 50     if(!fa[fa[x]]) { 51         if(!type){ 52             if(num[fa[x]]>1) other=(p[fa[x]]*(num[fa[x]]+0)-edge-F[x])/(num[fa[x]]-1)+edge; 53             else other=edge; 54         }else{ 55             other=(p[fa[x]]*(num[fa[x]]+2)-edge-F[x])/(num[fa[x]]+1)+edge; 56         } 57     } 58     else other=(p[fa[x]]*(num[fa[x]]+1)-edge-F[x])/num[fa[x]]+edge; 59       60     p[x]=(other+D[x])/(num[x]+1); 61     for(int i=H[x];i;i=X[i]){ 62         if(P[i]==fa[x]||oncircle[P[i]]) continue; 63         treedp2(P[i],E[i]); 64     } 65 } 66 vector<int> circle; 67 bool ok; 68 int nxt[100005];double wnxt[100005]; 69 void findcircle(int x,int fa){ 70     for(int i=H[x];i;i=X[i]){ 71         if(P[i]==fa) continue; 72         if(pre[P[i]]){ 73             ok=1; 74             int k=x; 75             pre[P[i]]=x; 76             wpre[P[i]]=E[i]; 77             do{ 78                 oncircle[k]=1; 79                 circle.push_back(k); 80                 k=pre[k]; 81             }while(k!=P[i]); 82             oncircle[k]=1; 83             circle.push_back(k); 84         }else{ 85             pre[P[i]]=x;wpre[P[i]]=E[i]; 86             findcircle(P[i],x); 87             if(ok) return; 88         } 89     } 90 } 91 double calc_nxt(int now,int end){ 92     double ret=wnxt[now]; 93     now=nxt[now]; 94     int extra=0; 95     if(nxt[now]!=end) ret+=calc_nxt(now,end)/(du[now]-1); 96     else extra=-1; 97     for(int i=H[now];i;i=X[i]){ 98         if(oncircle[P[i]]) continue; 99         ret+=(E[i]+F[P[i]])/(du[now]-1+extra);100     }101     return ret;102 }103 double calc_pre(int now,int end){104     double ret=wpre[now];105     now=pre[now];106     int extra=0;107     if(pre[now]!=end) ret+=calc_pre(now,end)/(du[now]-1);108     else extra=-1;109     for(int i=H[now];i;i=X[i]){110         if(oncircle[P[i]]) continue;111         ret+=(E[i]+F[P[i]])/(du[now]-1+extra);112     }113     return ret;114 }115 int main(){// the main function116     #ifdef LOCAL117     freopen("in.txt","r",stdin);118     freopen("out.txt","w",stdout);119     #endif120     scanf("%d%d",&n,&m);121     for(int i=0,x,y,z;i<m;i++){122         scanf("%d%d%d",&x,&y,&z);123         du[x]++;124         du[y]++;125         add(x,y,z);126         add(y,x,z);127     }128     if(m==n-1){129         treedp1(1);130         p[1]=F[1];131         for(int i=H[1];i;i=X[i]){132             treedp2(P[i],E[i]);133         }134         double ans=0;135         for(int i=1;i<=n;i++){136              ans+=p[i];137         }138         printf("%.5f\n",ans/n);139     }else{140         type=1;141         pre[1]=-1;142         findcircle(1,-1);143         for(int now=0;now<circle.size();now++){144             nxt[pre[circle[now]]]=circle[now];145             wnxt[pre[circle[now]]]=wpre[circle[now]];146         }147         for(int now=0;now<circle.size();now++){148             for(int i=H[circle[now]];i;i=X[i]){149                 if(oncircle[P[i]]) continue;150                 treedp1(P[i]);151                 p[circle[now]]+=(F[P[i]]+E[i])/du[circle[now]];152                 num[circle[now]]++;153             }154         }155         for(int now=0;now<circle.size();now++){156             p[circle[now]]+=(calc_pre(circle[now],circle[now])+calc_nxt(circle[now],circle[now]))/du[circle[now]];157         }158         for(int now=0;now<circle.size();now++){159             for(int i=H[circle[now]];i;i=X[i]){160                 if(oncircle[P[i]]) continue;161                 fa[P[i]]=circle[now];162                 treedp2(P[i],E[i]);163             }164         }165         double ans=0;166         for(int i=1;i<=n;i++){167             ans+=p[i];168         }169         printf("%.5f\n",ans/n);170     }171     return 0;172 }