首先我们知道MST的一些性质，对于这道题来说就是，假设我们先求出一颗MST设为G，由已知边权相同的边最多会有10条，那么假设我们在这10条边中选取size条边∈G，那么我们在这边权相同的边集E中任意选取size条有意义的边，这里的有意义的边的定义为每条边都会造成新的连通性的增加，那么边集E中所有的size条有意义的边的方案我们可以通过dfs求出，然后我们将不同边权的边的方案求连乘，就是MST的方案数。
ps：我们没有必要求一遍MST，我们可以一边做kruskal，一边维护图的连通性，然后每找到一个权值不同的边集E时深搜。
反思：做dfs的时候使用并查集维护图的连通性，但是加了路径压缩，这样就会在找块的祖先的时候改变不同节点的父亲，这样就没有办法在dfs时恢复原图，所以我们应该只用并查集维护节点的父亲而不是祖先，找了半天才找到这里的错误。
/**************************************************************
Problem: 1016
User: BLADEVIL
Language: C++
Result: Accepted
Time:8 ms
Memory:820 kb
****************************************************************/ //By BLADEVIL
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 110
#define maxm 1010
#define d39 31011 using namespace std; int n,m;
int father[maxn],curfather[maxn];
struct rec
{
int a,b,len;
} c[maxm]; bool cmp(rec a,rec b)
{return (a.len<b.len);} int getfather(int x)
{
if (father[x]==x) return x;
return father[x]=getfather(father[x]);
} int getcurfather(int x)
{
if (curfather[x]==x) return x;
return getcurfather(curfather[x]);
} int dfs(int l,int r,int size)
{
//printf("%d %d %d\n",l,r,size);
if (!size) return ;
if (l>r) return ;
int fa,fb,cur=;
cur=dfs(l+,r,size);
fa=getcurfather(c[l].a); fb=getcurfather(c[l].b);
if (fa!=fb)
{
curfather[fa]=fb;
cur+=dfs(l+,r,size-);
curfather[fa]=fa;
}
return cur;
} int main()
{
int ans=,cnt=;
scanf("%d%d",&n,&m);
for (int i=;i<=m;i++) scanf("%d%d%d",&c[i].a,&c[i].b,&c[i].len);
sort(c+,c+m+,cmp);
for (int i=;i<=n;i++) father[i]=curfather[i]=i;
int cur=;
int l,r,size=;
for (int i=;i<=m+;i++)
{
if (cur!=c[i].len)
{
r=i-;
//if (i!=1) printf(" %d %d %d\n",l,r,size);
if (i!=) ans=(ans*=dfs(l,r,size))%d39;
l=i;
size=;
cur=c[i].len;
memcpy(curfather,father,sizeof curfather);
}
int fa,fb;
fa=getfather(c[i].a); fb=getfather(c[i].b);
if (fa!=fb)
{
size++;
cnt++;
father[fa]=fb;
}
}
if (cnt!=n-) printf("0\n"); else printf("%d\n",ans);
return ;
}