图论之最小生成树计数（最小生成树的应用）-1.所有最小生成树的不同边权的数量一致。如一个图对应的所有最小生成树边权为1，2，3这样的边数固定不变，不会变成3条2，可以想象如果要换掉一条边，那么就必须那一条相等权的边换，大了就不是最小了，小了前一个就不是最小了。

2.相同边权的边所形成的联通块相同，可以想象kruskal建树过程，由小边到大边，小边够了之后联通块不变，等到有大边了，连通块才接着改变。

那么解题思路就变成了统计不同权边的使用方案数，再相乘即答案。

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=1010,mod=31011;
int n,m;
int p[N];
struct edge{
    int a,b,w;
    bool operator<(edge&W){
        return w<W.w;
    }
}e[M];
struct tree{
    int l,r,num,sum;
}t[M];
int idx;
int cnt;
int k;
int find(int x){
    if(x!=p[x]){
        return find(p[x]);
    }
    return x;
}
void dfs(int i,int q,int nu){
    if(nu==t[i].num){
        k++;
        return;
    }
    if(q>t[i].r){
        return;
    }
    int a=e[q].a;
    int b=e[q].b;
    int x=find(a);
    int y=find(b);
    if(x!=y){
        p[x]=y;
        dfs(i,q+1,nu+1);
        p[x]=x;
    }
    dfs(i,q+1,nu);
    return;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        e[i].a=a,e[i].b=b,e[i].w=c;
    }
    sort(e+1,e+1+m);
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    for(int i=1;i<=m;i++){
        int a=e[i].a;
        int b=e[i].b;
        int c=e[i].w;
        if(c!=e[i-1].w){
            idx++;
            t[idx].l=i;
            t[idx-1].r=i-1;
        }
        t[idx].sum++;
        int x=find(a);
        int y=find(b);
        if(x!=y){
            p[x]=y;
            t[idx].num++;
            cnt++;
        }
    }
    t[idx].r=m;
    if(cnt<n-1){
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++){
        p[i]=i;
    }
    int ans=1;
    for(int i=1;i<=idx;i++){
        //cout<<t[i].l<<endl;
        k=0;
        dfs(i,t[i].l,0);
        //cout<<k<<endl;
        if(k){
           ans=(long long )(ans*k)%mod;
        }
        for(int j=t[i].l;j<=t[i].r;j++){
            int a=e[j].a;
            int b=e[j].b;
            int x=find(a);
            int y=find(b);
            if(x!=y){
                p[x]=y;
            }
        }
    }
    cout<<ans;
}