#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define maxm 1005
#define maxn 105
#define mod 31011

int n,m,cnt,ans=1;
int fa[maxn],pos[maxn];
int K[maxn][maxn];
bool vis[maxn];

vector<int> v[maxn];

struct edge{
	int from,to,val;
	bool operator <(const edge &a)const{return val<a.val;}
}e[maxm];

inline int read(){
	int x=0;char ch=getchar();
	for (;ch<‘0‘||ch>‘9‘;ch=getchar());
	for (;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=x*10+ch-‘0‘;
	return x;
}

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

int gauss(){
	int t,n=cnt-1,ans=1,f=1;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			K[i][j]%=mod;
	for (int i=1;i<n;i++){
		for (t=i;t<=n;t++) if (K[t][i]) break;if (t>n) return 0;
		if (t!=i){for (int j=1;j<=n;j++) swap(K[i][j],K[t][j]);f=-f;}
		for (int j=i+1;j<=n;j++)
			for (;K[j][i];){
				int t=K[i][i]/K[j][i];
				for (int k=i;k<=n;k++) K[i][k]=(K[i][k]-t*K[j][k])%mod;
				for (int k=i;k<=n;k++) swap(K[i][k],K[j][k]);
				f=-f;
			}
	}
	for (int i=1;i<=n;i++) ans=1ll*ans*K[i][i]%mod;
	return ans*f;
}

void dfs(int x,int num){
	K[num][num]=v[x].size(),pos[x]=num;
	for (unsigned int i=0;i<v[x].size();i++){
		vis[v[x][i]]=0;
		if (!pos[v[x][i]]) pos[v[x][i]]=++cnt,K[num][pos[v[x][i]]]--,dfs(v[x][i],cnt);
		else K[num][pos[v[x][i]]]--;
	}
}

int main(){
	n=read(),m=read();
	for (int i=1;i<=m;i++) e[i].from=read(),e[i].to=read(),e[i].val=read();
	for (int i=1;i<=n;i++) fa[i]=i;
	sort(e+1,e+m+1);
	for (int i=1;i<=m+1;i++){
		int ck=find(1);
		for (int j=2;j<=n;j++) if (find(j)!=ck){ck=0;break;}
		if (ck) break;
		int x=find(e[i].from),y=find(e[i].to);
		if (x!=y) vis[x]=1,vis[y]=1,v[x].push_back(y),v[y].push_back(x);
		if (e[i].val!=e[i+1].val){
			for (int j=1;j<=n;j++)
				if (vis[j]){
					for (int a=1;a<=cnt;a++)
						for (int b=1;b<=cnt;b++)
							K[a][b]=0;
					memset(pos,0,sizeof(pos));
					vis[j]=0,cnt=1,dfs(j,cnt);
					ans=1ll*ans*gauss()%mod;
				}
			for (int j=1;j<=n;j++){
				for (unsigned int k=0;k<v[j].size();k++){
					int x=find(j),y=find(v[j][k]);
					if (x!=y) fa[x]=y;
				}
				v[j].clear();
			}
		}
	}
	int check=find(1);
	for (int i=2;i<=n;i++) if (find(i)!=check){check=0;break;}
	printf("%d\n",check?ans:0);
	return 0;
}