#include<bits/stdc++.h>
using namespace std;
const int MOD=31011;
int n,m,f[101],sl,ans=1,flag[101];
unordered_map<int,int> m1;
unordered_map<int,int> m3;
map<pair<int,int>,bool> m2; 
struct edge{
    int l,r,w;
}a[1001];
bool cmp(edge x,edge y){
    return x.w<y.w;
}
int fid(int x){
    return f[x]= x==f[x]?x:fid(f[x]);
}
void merge(int x,int y){
    int f1=fid(x),f2=fid(y);
    if(f1!=f2) f[f1]=f2;
}
int dfs(int i,int j,int dq,int zg){
    if(dq>zg) return 1;
    if(zg-dq>j-i+1) return 0;
    int sum=0;
    for(int l=i;l<=j;l++){
        int u=a[l].l,v=a[l].r,w=a[l].w;
        if(m2[{m1[w],u}] && m2[{m1[w],v}] && (!flag[u] || !flag[v])){
            if(!flag[u] && !flag[v]){
                flag[u]=flag[v]=1;
                sum=(sum+dfs(l+1,j,dq+1,zg))%MOD;
                flag[u]=flag[v]=0;
            }
            else if(!flag[u]){
                flag[u]=1;
                sum=(sum+dfs(l+1,j,dq+1,zg))%MOD;
                flag[u]=0;
            }
            else if(!flag[v]){
                flag[v]=1;
                sum=(sum+dfs(l+1,j,dq+1,zg))%MOD;
                flag[v]=0;
            }
        }
    }
    return sum;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        cin>>a[i].l>>a[i].r>>a[i].w;
    }
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++){
        int u=a[i].l,v=a[i].r,w=a[i].w;
        if(fid(u)!=fid(v)){
            sl++;
            merge(u,v);
            if(!m1[w]) m1[w]=i;
            m3[w]++;
            m2[{m1[w],u}]=m2[{m1[w],v}]=1;
        }
    }
    if(sl!=n-1){
        cout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;){
        int j=i;
        while(j<=m && a[j].w==a[i].w) j++;
        if(m3[a[i].w]){
            memset(flag,0,sizeof(flag));
            ans=(ans*dfs(i,j-1,1,m3[a[i].w]))%MOD;
            for(int k=i;k<j;k++){
                int u=a[k].l,v=a[k].r;
                if(m2[{m1[a[i].w],u}] && m2[{m1[a[i].w],v}]){
                    merge(u,v);
                }
            }
        }
        i=j;
    }
    cout<<ans;
    return 0;
}