#1 AC,思路混乱

#include<bits/stdc++.h>
using namespace std;
int a,d[10001],aa[1001][1001],b,k[10001],kk[10001],fa[10001],x[10001],y[10001],z[10001],ans=1;bool vis[10001];
int fnd(int i){
	if(fa[i]==i) return i;
	else return fa[i]=fnd(fa[i]);
}
void prim(){
	memset(d,0x3f,sizeof d);
	int t=0;
	d[1]=0;
	while(++t<a){
		int p=0;
		for(int i=1;i<=a;i++){
			if((d[i]<d[p]||p==0)&&!vis[i]){
				p=i;
			}
		}
		vis[p]=1;
		for(int i=1;i<=a;i++){
			if(!vis[i]){
				d[i]=min(d[i],aa[p][i]);
			}
		}
	}
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>a>>b;
    memset(aa,0x3f,sizeof aa);
    for(int i=1;i<=b;i++){
    	cin>>x[i]>>y[i]>>z[i];
    	aa[x[i]][y[i]]=z[i];
    	aa[y[i]][x[i]]=z[i];
    	kk[z[i]]++;
	}
	prim();
	for(int i=1;i<=a;i++){
		if(d[i])
		k[d[i]]++;	
	}
	for(int i=1;i<=a;i++){
		fa[i]=i;
	}
	int sum;
	for(int o=1;o<=a&&k[o];o++){
		int w=d[o];
		int n=k[o];
		if(w==0||k[w]==0) continue;
		k[d[o]]=max(k[d[o]],kk[d[o]]-k[d[o]]);
		sum=0;
		for(int i=1;i<=b;i++){
			if(z[i]==w&&fnd(x[i])!=fnd(y[i])){
				sum++;
			}
		}
		if(sum>=k[w]){
			ans=(ans*sum)%31011;
		}
		int xx=0;
		for(int i=1;i<=b&&xx<k[w];i++){
			if(z[i]==w&&fnd(x[i])!=fnd(y[i])){
				fa[fnd(x[i])]=fnd(y[i]);
				xx++;
			}
		}
	}
	cout<<ans;
}