求调qaq

#include<bits/stdc++.h>
using namespace std;
#define int long long
using PII=pair<int,int>;
using db=double;
using Double=long double;
#define TLC (db)clock()/CLOCKS_PER_SEC<0.91
#define pb push_back
#define eb emplace_back
#define PQ priority_queue
#define fi first
#define se second
#define smax(a,b) (a=max(a,b))
#define smin(a,b) (a=min(a,b))
#define File(str) \
	freopen(str".in","r",stdin);\
	freopen(str".out","w",stdout)
#define Dbg(fmt,...) \
	fprintf(stderr,"[%s:%d %s]" fmt "\n",__FILE__,__LINE__,__FUNCTION__,##__VA_ARGS__)
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define irep(i,x,y) for(int i=y;i>=x;--i)
#define V vector
#define W while
#define S0(x) memset(x,0,sizeof(x))
#define Set(x,y) memset(x,y,sizeof(x))
#define endl '\n'
const int N=1010,P=31011;
/*
Ask how much MST does a Non-Directed Graph have.
First,get a MST using kruskal's. Mark the different nodes. 
and the usings of each weighted edge.
if edge != n-1 print 0. else dfs to get all possible link ways
(using equal, weight equal Dfs)
*/
int n,m,cnt,buc[N],x[N],y[N],fa[N];
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
struct edge{
	int u,v,w;
	bool operator<(const edge&a)const{
		return w<a.w;
	}
}e[N];
int Dfs(int u,int cnt,int idx){
	if(u>y[idx])
		return cnt==buc[idx];
	int fu=find(e[u].u),fv=find(e[u].v);
	int ret=0;
	if(fu!=fv){
		fa[fu]=fv;
		ret+=Dfs(u+1,cnt+1,idx);
		fa[fu]=fu,fa[fv]=fv;
	}
	return ret+Dfs(u+1,cnt,idx);
}
void Init(){
	cnt=0,S0(buc);
	cin>>n>>m;
	rep(i,1,m)cin>>e[i].u>>e[i].v>>e[i].w;
}
void reset(){
	iota(fa,fa+n+1,0);
}
void Solve(){
	Init();
	sort(e+1,e+m+1);
	reset();
	int tot=0;
	rep(i,1,m){
		if(e[i].w!=e[i-1].w)
			y[cnt]=i-1,x[++cnt]=i;
		int fu=find(e[i].u),fv=find(e[i].v);
		if(fu!=fv)
			++buc[cnt],fa[fu]=fv,++tot;
	}
	y[cnt]=m;
	if(tot!=n-1){
		cout<<"0\n";
		return;
	}	
	reset();
	int ans=1;
	rep(i,1,cnt){
		ans=ans*Dfs(x[i],0,i)%P;
		rep(j,x[i],y[i])
			fa[find(e[j].u)]=find(e[j].v);
	}
	cout<<ans<<endl;
}
main(){
	cin.tie(0)->sync_with_stdio(0);
	int T=1;
	//cin>>T;
	while(T--)
		Solve();
}