1 #include<cstdio>  2     3 #include<cstdlib>  4     5 #include<cmath>  6     7 #include<cstring>  8     9 #include<algorithm> 10    11 #include<iostream> 12    13 #include<vector> 14    15 #include<map> 16    17 #include<set> 18    19 #include<queue> 20    21 #include<string> 22    23 #define inf 1000000000 24    25 #define maxn 200+5 26    27 #define maxm 200000+5 28    29 #define eps 1e-10 30    31 #define ll long long 32    33 #define pa pair<int,int> 34    35 #define for0(i,n) for(int i=0;i<=(n);i++) 36    37 #define for1(i,n) for(int i=1;i<=(n);i++) 38    39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40    41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42    43 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go) 44    45 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) 46    47 #define mod 1000000007 48    49 using namespace std; 50    51 inline int read() 52    53 { 54    55     int x=0,f=1;char ch=getchar(); 56    57     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 58    59     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 60    61     return x*f; 62    63 } 64 int n,m,k,tot,d[maxn],head[maxn]; 65 struct edge{int go,next,w;}e[maxm]; 66 inline void add(int x,int y,int w) 67 { 68     e[++tot]=(edge){y,head[x],w};head[x]=tot; 69 } 70 double ans,a[maxn][maxn]; 71 inline void gauss() 72 { 73     //for1(i,n){for1(j,n+1)cout<<a[i][j]<<‘ ‘;cout<<endl;} 74     for1(i,n) 75     { 76         int k=i; 77         for2(j,i+1,n)if(fabs(a[j][i])>fabs(a[k][i]))k=j; 78         for2(j,i,n+1)swap(a[i][j],a[k][j]); 79         for2(j,i+1,n) 80         { 81           double t=a[j][i]/a[i][i]; 82           for2(x,i,n+1)a[j][x]=a[i][x]*t-a[j][x]; 83         } 84     } 85     //for1(i,n){for1(j,n+1)cout<<a[i][j]<<‘ ‘;cout<<endl;} 86     for3(i,n,1) 87     { 88         //cout<<a[i][i]<<‘ ‘<<a[i][n+1]<<"fuck"<<endl; 89         for2(j,i+1,n)a[i][n+1]-=a[i][j]*a[j][n+1]; 90         a[i][n+1]/=a[i][i]; 91         //cout<<i<<‘ ‘<<a[i][n+1]<<endl; 92     } 93 } 94    95 int main() 96    97 { 98     n=read();m=read(); 99     for1(i,m)100     {101         int x=read(),y=read(),w=read();102         if(x!=y){d[x]++;d[y]++;add(x,y,w);add(y,x,w);}103         else {d[x]++;add(x,x,w);}104     }105     for0(j,30)106     {107         memset(a,0,sizeof(a));108         for1(x,n-1)109         {110             a[x][x]=-1.0;111             double t=1.0/(double)d[x];112             for4(i,x)113             if(e[i].w>>j&1)a[x][n+1]-=t,a[x][y]-=t;114             else a[x][y]+=t;115         }116         a[n][n]=1.0;117         gauss();118         //cout<<a[1][n+1]<<‘ ‘<<(1<<j)<<endl;119         ans+=a[1][n+1]*(1<<j);120     }121     printf("%.3f\n",ans);122   123     return 0;124   125 }