rt：
思路就是，把权值不等于 $val_i$ 的边的两端塞进一个连通块里，相当于缩点，最后连边，用高斯消元（非质数取模）求解
不知道哪里出了问题

#include<bits/stdc++.h>
using namespace std;
const int MOD=31011;
const int sze=3010;
int n,m,tot=0,cnt=0,ans=1;
int fa[sze],col[sze],val[sze],a[1010][1010];
struct node{
	int u,v,w;
	inline void input(){cin>>u>>v>>w;}
}edge[sze],OnTree[sze];
inline bool cmp(const node &x,const node &y){return x.w<y.w;}
int Get(int x){return (x==fa[x])?x:(fa[x]=Get(fa[x]));}
inline void add(int x,int y){--a[x][y],--a[y][x],++a[x][x],++a[x][y];}
namespace n1{
	inline int work(int n){
		int ans=1;
		for(int i=1;i<=n;++i){
			for(int j=i+1;j<=n;++j){
				while(a[j][i]){
					int rate=a[i][i]/a[j][i];
					for(int k=1;k<=n+1;++k) a[i][k]=(a[i][k]-1ll*a[j][k]*rate%MOD+MOD)%MOD;
					swap(a[i],a[j]),ans=-ans;
				}
			}
			ans=1ll*ans*a[i][i]%MOD;
			ans=(ans+MOD)%MOD;
		}
		return ans;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=m;++i) edge[i].input();
	for(int i=1;i<=n;++i) fa[i]=i;
	sort(edge+1,edge+m+1,cmp);
	for(int i=1;i<=m;++i){
		int fx=Get(edge[i].u),fy=Get(edge[i].v);
		if(fx==fy) continue;
		fa[fx]=fy,OnTree[++cnt]=edge[i];
		if(edge[i].w!=val[tot]) val[++tot]=edge[i].w;
	}
	if(cnt!=n-1) return cout<<"0\n",0;
	for(int i=1;i<=tot;++i){
		for(int i=1;i<=n;++i) fa[i]=i;
		for(int i=1;i<=n-1&&OnTree[i].w!=val[i];++i) fa[Get(OnTree[i].u)]=Get(OnTree[i].v);
		for(int i=n-1;i>=1&&OnTree[i].w!=val[i];--i) fa[Get(OnTree[i].u)]=Get(OnTree[i].v);
		int cc=0;
		for(int i=1;i<=n;++i) if(Get(i)==i) col[i]=++cc;
		for(int i=1;i<=n;++i) col[i]=col[Get(i)];
		memset(a,0,sizeof(a));
		for(int i=1;i<=m;++i) if(edge[i].w==val[i]) add(col[edge[i].u],col[edge[i].v]);
		ans=1ll*ans*n1::work(cc-1)%MOD;
	}
	cout<<ans%MOD<<'\n';
	return 0;
}