1 type node1=record 2      x,y,w:longint; 3      end; 4      node2=record 5      l,r,v:longint; 6      end; 7 var e:array[0..2000] of node1; 8     a:array[0..2000] of node2; 9     i,n,m,ans,sum,xx,yy,cnt,tot,j:longint;10     fa:array[0..2000] of longint;11 function find(x:longint):longint;12  begin13  if fa[x]<>x then fa[x]:=find(fa[x]);14  exit(fa[x]);15  end;16 procedure qsort(h,l:longint);17  var i,j,m:longint;18      tmp:node1;19  begin20  i:=h;j:=l;m:=e[(i+j)>>1].w;21  repeat22   while e[i].w<m do inc(i);23   while e[j].w>m do dec(j);24   if i<=j then25    begin26    tmp:=e[i];e[i]:=e[j];e[j]:=tmp;27    inc(i);dec(j);28    end;29  until i>j;30  if i<l then qsort(i,l);31  if j>h then qsort(h,j);32  end;33 procedure init;34  begin35  readln(n,m);36  for i:=1 to m do with e[i] do readln(x,y,w);37  qsort(1,m);38  cnt:=0;tot:=0;39  for i:=1 to n do fa[i]:=i;40  for i:=1 to m do41   begin42   if e[i].w<>e[i-1].w then43    begin44    a[cnt].r:=i-1;45    inc(cnt);46    a[cnt].l:=i;47    end;48   xx:=find(e[i].x);yy:=find(e[i].y);49   if xx<>yy then50    begin51    fa[xx]:=yy;52    inc(a[cnt].v);53    inc(tot);54    end;55   end;56  a[cnt].r:=m;57  if tot<n-1 then begin writeln(0);halt;end;58  end;59 procedure dfs(x,now,k:longint);60  var xx,yy:longint;61  begin62  if now=a[x].r+1 then63   begin64   if k=a[x].v then inc(sum);65   exit;66   end;67  xx:=find(e[now].x);yy:=find(e[now].y);68  if xx<>yy then69   begin70   fa[xx]:=yy;71   dfs(x,now+1,k+1);72   fa[xx]:=xx;fa[yy]:=yy;73   end;74  dfs(x,now+1,k);75  end;76 procedure main;77  begin78  for i:=1 to n do fa[i]:=i;79  ans:=1;80  for i:=1 to cnt do81   begin82   sum:=0;83   dfs(i,a[i].l,0);84   ans:=(ans*sum) mod 31011;85   for j:=a[i].l to a[i].r do86    begin87    xx:=find(e[j].x);yy:=find(e[j].y);88    if xx<>yy then fa[xx]:=yy;89    end;90   end;91  writeln(ans);92  end;93 begin94  init;95  main;96 end.