#define MOD 31011
using namespace std;
struct node{
	int u,v,w;
};
int n,m,f[101],l[1001],r[1001],cnt,exc[1001],d[1001],tot,xx,yy,ans;
bool flag;
node e[1001];
int find(int x){
	return f[x] == x ? x : f[x] = find(f[x]);
}
bool cmp(node a,node b){
	return a.w < b.w;
}
void kru(){
	for(int i = 1;i <= n;i ++){
		f[i] = i;
	}
	for(int i = 1;i <= m;i ++){
		xx = find(e[i].u);
		yy = find(e[i].v);
		if(xx == yy){
			continue;
		}
		f[yy] = xx;
		d[exc[i]] ++;
		tot ++;
		if(tot == n - 1){
			flag = true;
			return;
		}
	}
	printf("0");
	return;
}
void sch(int st,int alr,int w){
	if(st > r[w]){
		if(alr == d[w]){
			tot ++;
			tot %= MOD;
		}
		return;
	}
	int p[101];
	for(int i = 1;i <= n;i ++){
		p[i] = f[i];
	}
	xx = find(e[st].u),yy = find(e[st].v);
	if(xx != yy){
		f[yy] = xx;
		sch(st + 1,alr + 1,w);
	}
	for(int i = 1;i <= n;i ++){
		f[i] = p[i];
	}
	sch(st + 1,alr,w);
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i ++){
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	}
	sort(e + 1,e + m + 1,cmp);
	for(int i = 1;i <= m;i ++){
		if(e[i].w == e[i - 1].w){
			r[cnt] ++;
		}
		else{
			l[++ cnt] = r[cnt] = i;
		}
		exc[i] = cnt;
	}
	kru();
	if(!flag){
		return 0;
	}
	for(int i = 1;i <= n;i ++){
		f[i] = i;
	}
	ans = 1;
	for(int i = 1;i <= cnt;i ++){
		if(d[i]){
			tot = 0;
			sch(l[i],0,i);
			ans *= tot;
			ans %= MOD;
		}
		for(int j = l[i];j <= r[i];j ++){
			xx = find(e[j].u),yy = find(e[j].v);
			if(xx != yy){
				f[yy] = xx;
			}
		}
	}
	printf("%d",ans);
	return 0;
}```