#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<iostream>
#include<string>
#include<cmath>
#define M 1000100
#define MOD 31011
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
typedef long long LL;
using namespace std;
struct edge{int x,y,z;}e[M];
bool cmp(edge a,edge b){return a.z<b.z;}
int len=0,b[M],va[M],cnt[M],eva[M],st[M],ed[M],f[M],n,m,sum,elen=0,Len=0,bst[M],bed[M],bb[M];
void initf(){int i;FOR(i,1,n) f[i]=i;}
int getf(int x)
{
  if (f[x]!=x) f[x]=getf(f[x]);
  return f[x];
}
int getf2(int x)
{
  if (f[x]!=x) return getf2(f[x]);
  return x;
}
void dfs(int L,int R,int x,int tar)
{
  if (x==tar) {++sum;return;}
  if (L>R) return;
  int fx=getf2(e[L].x),fy=getf2(e[L].y);
  if (fx!=fy)
  {
    f[fx]=fy;
    dfs(L+1,R,x+1,tar);
    f[fx]=fx;
  }
  dfs(L+1,R,x,tar);
}
int gp(int x){return lower_bound(eva+1,eva+1+elen,x)-eva;}
int main()
{
  scanf("%d%d",&n,&m);
  int i,t1,t2,t3,j;
  FOR(i,1,m)
  {
    scanf("%d%d%d",&t1,&t2,&t3);
    e[i].x=t1;e[i].y=t2;e[i].z=t3;
  }
  sort(e+1,e+1+m,cmp);
  initf();int ct=0;
  FOR(i,1,m)
  {
    int fx=getf(e[i].x),fy=getf(e[i].y);
    if (fx!=fy)
    {
      f[fx]=fy;
      b[++ct]=e[i].z;bb[ct]=i;
      if (ct==n-1) break;
    }
  }
  if (ct!=n-1) {printf("0\n");return 0;}
  int last=-1;
  FOR(i,1,ct)
  {
    if (b[i]==last) cnt[Len]++;
    else {bed[Len]=i-1;last=b[i];bst[++Len]=i;cnt[Len]=1;va[Len]=b[i];}
  }bed[Len]=ct;
  last=-1;
  initf();
  FOR(i,1,m)
  {
    if (e[i].z==last) {}
    else {ed[elen]=i-1;last=e[i].z;st[++elen]=i;eva[elen]=e[i].z;}
  }ed[elen]=m;
  LL ans=1;
  FOR(i,1,Len)
  {
    int p=gp(va[i]);
    sum=0;
    dfs(st[p],ed[p],0,cnt[i]);
    FOR(j,bst[i],bed[i]) 
    {
      int fx=getf(e[bb[j]].x),fy=getf(e[bb[j]].y);
      f[fx]=fy;
    }
    ans*=sum;ans%=MOD;
  }
  printf("%lld\n",ans);
}