本来是Matrix-Tree裸题，然后不知道怎么写挂了，然后再网上看到了一种奇怪的做法：

首先处理出一棵最小生成树，然后统计不同权值在树上的出现的次数，

有个性质是显然的：最小生成树上的不同权值的个数一定是上面那样子的（虽然不会证但是总感觉很有道理）

然后就按权值从小到大，处理出权值为v的所有边的不会使当前图有环的方案s，然后选择其中一种方案的边加入当前图中，最后把所有s乘起来。

至于证明：数学归纳法假设前i种权值选择好了之后的图联通情况都是相同的，然后加入k条边，如果有两种方案使得处理后联通情况不同那么两种方案的并一定会更优，所以是可以这么搞的。然后这么看所有权值的边选择独立，所以可以乘法原理乘起来。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 105
#define M 31011
struct Line
 {
 	int x,y,v;
 } a[N*10];
int n,m,ss=1,fa[N],s[N*10],cnt=0,h[N*10],ans=1;
bool b[N*10];
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
int Find(int x)
 {return x==fa[x]?x:(fa[x]=Find(fa[x]));}
inline bool cmp(Line x,Line y)
 {return x.v<y.v;}
int find(int x)
 {return x==fa[x]?x:find(fa[x]);}
int DFS(int x,int y,int z)
 {
 	int i=find(a[x].x),j=find(a[x].y),k=0;
 	if (x==z) return y==0;
 	if (i!=j&&y) {fa[i]=j;k=DFS(x+1,y-1,z);fa[i]=i;}
 	k+=DFS(x+1,y,z);
 	return k;
 }
int main()
 {
 	int i,j,k,l,q,w,e=0;
 	n=Read();m=Read();
 	for (i=1;i<=m;i++)
 	  a[i].x=Read(),a[i].y=Read(),a[i].v=Read();
 	sort(a+1,a+m+1,cmp);
 	for (i=1;i<=n;i++) fa[i]=i;
 	for (i=1;i<=m;i++)
 	 {
 	 	k=Find(a[i].x);l=Find(a[i].y);
 	 	if (k!=l)
 	 	  fa[k]=l,e++,b[i]=1;
 	 }
 	if (e!=n-1)
 	 {printf("0\n");return 0;}
 	for (i=1;i<=m;i++)
 	 {
 	 	if (a[i].v!=a[i-1].v) h[++cnt]=i;
 	 	s[cnt]+=b[i];
 	 }
 	h[cnt+1]=m+1;
 	for (i=1;i<=n;i++) fa[i]=i;
 	for (i=1;i<=cnt;i++)
 	 {
 	    ans=(ans*DFS(h[i],s[i],h[i+1]))%M;
 	    for (j=h[i];j<h[i+1];j++)
 	     if (b[j])
 	       q=find(a[j].x),w=find(a[j].y),fa[q]=w;
 	 }
 	cout <<ans<<endl;
 	return 0;
 }