思路

按Kruskal同权块保留收缩前并查集，先算本块必选秩，再枚举最多10条同权边中无环且秩满足的子集，乘法计数并取模31011；不能将同权边逐条贪心后只计一种，原图简单但收缩后平行边必须区分。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DSU{vector<int>p,s;int parts;DSU(int n):p(n),s(n,1),parts(n){iota(p.begin(),p.end(),0);}int find(int x){return p[x]==x?x:p[x]=find(p[x]);}bool join(int a,int b){a=find(a);b=find(b);if(a==b)return false;if(s[a]<s[b])swap(a,b);p[b]=a;s[a]+=s[b];parts--;return true;}};
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<tuple<int,int,int>>e;while(m--){int u,v,w;cin>>u>>v>>w;e.push_back({w,u-1,v-1});}sort(e.begin(),e.end());DSU ds(n);long long ans=1;for(int l=0;l<(int)e.size();){int rr=l;while(rr<(int)e.size()&&get<0>(e[rr])==get<0>(e[l]))rr++;DSU end=ds;for(int i=l;i<rr;i++)end.join(get<1>(e[i]),get<2>(e[i]));int need=ds.parts-end.parts,ways=0;for(int mask=0;mask<(1<<(rr-l));mask++){if(__builtin_popcount((unsigned)mask)!=need)continue;DSU trial=ds;bool ok=true;for(int j=0;j<rr-l;j++)if(mask>>j&1)if(!trial.join(get<1>(e[l+j]),get<2>(e[l+j])))ok=false;if(ok)ways++;}ans=ans*ways%31011;ds=end;l=rr;}cout<<(ds.parts==1?ans:0)<<'\n';}