1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 int n,m; 5 struct Disjoint_Set 6 { 7     int fa[101],rank[101]; 8     void init(){for(int i=1;i<=n;i++) fa[i]=i;} 9     int findroot(int x) 10       {11         if(fa[x]==x) return x;12         int rt=findroot(fa[x]);13         fa[x]=rt;14         return rt;15       }16     void Union(int U,int V)17       {18         if(rank[U]<rank[V]) fa[U]=V;19         else20           {21             fa[V]=U;22             if(rank[U]==rank[V]) rank[U]++;23           }24       }25 };26 Disjoint_Set S,used;27 struct Edge{int u,v,w;};28 bool cmp(const Edge &a,const Edge &b){return a.w<b.w;}29 Edge edges[1001];30 int res,ans=1,tot,cnt,sta,end;31 void dfs(int cur,int sum,Disjoint_Set now)32 {33     if(cur>end)34       {35           if(sum==cnt) res++;36           return;37       }38     dfs(cur+1,sum,now);39     int f1=now.findroot(edges[cur].u),f2=now.findroot(edges[cur].v);40     if(f1!=f2) {now.Union(f1,f2); dfs(cur+1,sum+1,now);}41 }42 int main()43 {44     scanf("%d%d",&n,&m);45     for(int i=1;i<=m;i++) scanf("%d%d%d",&edges[i].u,&edges[i].v,&edges[i].w);46     sort(edges+1,edges+m+1,cmp);47     S.init();used.init();48     for(int i=1;i<=m;i++)49       {50           if(edges[i].w!=edges[i-1].w) {used=S; cnt=0; sta=i;}51           int f1=S.findroot(edges[i].u),f2=S.findroot(edges[i].v);52           if(f1!=f2) {S.Union(f1,f2); tot++; cnt++;}53           if(edges[i].w!=edges[i+1].w)54             {55                 res=0; end=i;56                 dfs(sta,0,used);57                 ans=((ans%31011)*(res%31011))%31011;58             }59           else if(tot==n-1)60             {61                 res=0;62                 for(int j=i+1;j<=m;j++)63                   if(edges[j].w!=edges[i].w)64                     {65                       end=j-1;66                       goto OUT;67                     }68                 end=m;69                 OUT:dfs(sta,0,used);70                 ans=((ans%31011)*(res%31011))%31011;71                 break;72             }73       }74     printf("%d\n",tot==n-1 ? ans : 0);75     return 0;76 }