#include<bits/stdc++.h>
using namespace std;
const int N=110,M=1e3+5;
const int mod=31011;
struct node{
	int x,y,c;
}a[M];
bool cmp(node n1,node n2){
	return n1.c<n2.c;
}
int fa[N],siz[N];
int get(int x){//并查集
	if(fa[x]==x)return x;
	return get(fa[x]);
}
void merge(int tx,int ty){
	if(siz[tx]>siz[ty])swap(tx,ty);
	fa[tx]=ty;
	siz[ty]+=siz[tx];
}
int cnt,sum,l[M],r[M],c[M];
//l数组表示当前权值相同的一段的左端点
//r数组表示当前权值相同的一段的右端点
//c数组表示最小生成树内当前权值的边需要多少条 
void dfs(int pos,int now,int num){
	if(pos==r[now]+1){
		if(num==c[now])sum++;
		return;
	}
	int x=a[pos].x,y=a[pos].y;
	int tx=get(x),ty=get(y);
	if(tx!=ty){
		merge(tx,ty);
		dfs(pos+1,now,num+1);
		siz[ty]-=siz[tx];
		fa[tx]=tx,fa[ty]=ty;
		//敲重点！！！
		//这里由于进行了回溯操作，因此实际上是一个可撤销并查集
		//需要用一个栈来记录并查集的操作
		//但是由于dfs本身就是栈序的，可以不需要额外开栈
		//可撤销并查集记得不能路径压缩，不然你并查集内儿子节点部分就更新不到了
		//不过为了保证时间复杂度，这里采用了按秩合并优化 
	}
	dfs(pos+1,now,num);
}
int main(){
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
	}
	sort(a+1,a+m+1,cmp);//排序 
	for(int i=1;i<=n;i++){//初始化 
		fa[i]=i;
		siz[i]=1;
	}
	int tot=0;
	for(int i=1;i<=m;i++){//kruskal 
		if(a[i].c!=a[i-1].c){
			r[cnt]=i-1;
			l[++cnt]=i;
		}
		int x=a[i].x,y=a[i].y;
		int tx=get(x),ty=get(y);
		if(tx!=ty){
			merge(tx,ty);
			c[cnt]++;
			tot++;
		}
	}
	r[cnt]=m;
	if(tot!=n-1){//不构成最小生成树，特判 
		puts("0");
		return 0;
	}
	for(int i=1;i<=n;i++){
		fa[i]=i;
		siz[i]=1;
	}
	int ans=1;
	for(int i=1;i<=cnt;i++){
		sum=0;
		dfs(l[i],i,0);//搜索 
		ans=ans*sum%mod;//乘法原理 
		for(int j=l[i];j<=r[i];j++){//由于搜索时进行了回溯操作，因此要让并查集维持原样 
			int x=a[j].x,y=a[j].y;
			int tx=get(x),ty=get(y);
			if(tx!=ty){
				merge(tx,ty);
			}
		}
	}
	printf("%d",ans);
	return 0;
}