1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 #include<cmath> 7 using namespace std; 8 const int mxn=20010; 9 int read(){10     int x=0,f=1;char ch=getchar();11     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12     while(ch>=‘0‘ && ch<=‘9‘){x=x*10-‘0‘+ch;ch=getchar();}13     return x*f;14 }15 struct edge{16     int v,nxt,w;17 }e[mxn<<1];18 int hd[mxn],mct=0;19 void add_edge(int u,int v,int w){20     e[++mct].nxt=hd[u];e[mct].v=v;e[mct].w=w;hd[u]=mct;return;21 }22 int deg[mxn];23 int n,m;24 double f[300][300];25 void Gauss(){26     int i,j,k;27     for(i=1;i<=n;i++){28         int p=i;29         for(j=i+1;j<=n;j++)30             if(fabs(f[j][i])>fabs(f[p][i]))p=j;31         if(p!=i)for(k=i;k<=n+1;k++)swap(f[i][k],f[p][k]);32         for(j=i+1;j<=n;j++){33             double c=f[j][i]/f[i][i];34             for(k=i;k<=n+1;k++){35                 f[j][k]-=f[i][k]*c;36             }37         }38     }39     for(i=n;i;i--){40         double res=0;41         for(j=i+1;j<=n;j++){42             res+=f[j][n+1]*f[i][j];43         }44         f[i][n+1]=(f[i][n+1]-res)/f[i][i];45     }46     return;47 }48 int main(){49     int i,j,u,v,w;50     n=read();m=read();51     for(i=1;i<=m;i++){52         u=read();v=read();w=read();53         add_edge(u,v,w);deg[u]++;54         if(u!=v){add_edge(v,u,w);deg[v]++;}55     }56     double ans=0;57     for(i=0;i<31;i++){58         memset(f,0,sizeof f);59         for(j=1;j<=n;j++)f[j][j]=1;60         for(j=1;j<n;j++){61             for(int k=hd[j];k;k=e[k].nxt){62                 int v=e[k].v;63                 if((e[k].w>>i)&1){64                     f[j][v]+=1/(double)deg[j];65                     f[j][n+1]+=1/(double)deg[j];66                 }67                 else f[j][v]-=1/(double)deg[j];68             }69         }70         Gauss();71         ans+=f[1][n+1]*(1<<i);72     }73     printf("%.3f\n",ans);74     return 0;75 }