题解

#include<bits/stdc++.h>
using namespace std;
const int N=120,M=1020,mod=31011;
int n,m,x[M],tot,ans,num[M],fa[N],ct;
vector <int> p[M];
struct node{
    int u,v,w;
}e[M];
bool cmp(node a,node b){
    return a.w<b.w;
}
int find(int x){
    if(fa[x]==x) return x;
    return find(fa[x]);
}
void kruskal(){
    sort(e+1,e+1+m,cmp);int pt=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1,u,v,eu,ev;i<=m;i++){
        u=e[i].u;eu=find(u);
        v=e[i].v;ev=find(v);
        if(eu==ev) continue;
        fa[eu]=ev;
        int h=lower_bound(x+1,x+1+tot,e[i].w)-x;
        num[h]++;pt++;
    }
    if(pt<n-1){
        puts("0");
        exit(0);
    }
    for(int i=1;i<=n;i++) fa[i]=i;
}
void dfs(int now,int cnt,int pos){
    if(cnt==num[now]){
        ct++;if(ct>mod) ct-=mod;return;
    }
    if(pos==p[now].size()){
        return;
    }
    int pre[N];
    for(int i=1;i<=n;i++) pre[i]=fa[i];
    int eu=find(e[p[now][pos]].u),ev=find(e[p[now][pos]].v);
    if(eu!=ev){
        fa[ev]=eu;
        dfs(now,cnt+1,pos+1);
    }
    for(int i=1;i<=n;i++) fa[i]=pre[i];    
    dfs(now,cnt,pos+1);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>e[i].u>>e[i].v>>e[i].w,x[i]=e[i].w;
    sort(x+1,x+1+m);tot=unique(x+1,x+1+m)-x-1;
    kruskal();ans=1;
    for(int i=1;i<=m;i++){
        int h=lower_bound(x+1,x+1+tot,e[i].w)-x;
        p[h].push_back(i);
    }
    
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=tot;i++){
        if(!num[i]) continue;
        dfs(i,0,0);
        ans=ans*ct%mod;ct=0;
        for(int k:p[i]){
            int u=e[k].u,v=e[k].v;
            if(find(u)!=find(v)) fa[find(u)]=find(v);
        }
    }
    cout<<ans;
    return 0;
}