这道题主要利用了最小生成树的两个性质
最小生成树每种边权的数目固定不变
最小生成树每种边权带来的连通状况一定唯一
由于每种边权的只有不到10种，所以直接穷举然后乘法原理即可
const mo=;
type node=record
x,y,w:longint;
end; var a:array[..] of node;
fa,rank,v:array[..] of longint;
sum,ans,k1,k2,s,i,j,n,m,p,k:longint; function getf(x:longint):longint;
begin
if fa[x]<>x then fa[x]:=getf(fa[x]);
exit(fa[x]);
end; procedure swap(var a,b:node);
var c:node;
begin
c:=a;
a:=b;
b:=c;
end; procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
i:=l;
j:=r;
x:=a[(l+r) shr ].w;
repeat
while a[i].w<x do inc(i);
while x<a[j].w do dec(j);
if not(i>j) then
begin
swap(a[i],a[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; function calc(x:longint):longint;
begin
calc:=;
while x> do
begin
calc:=calc+x mod ;
x:=x shr ;
end;
end; function check(p,cur:longint):longint;
var i,res,tot:longint;
begin
for i:= to n do
fa[i]:=i;
tot:=;
res:=;
for i:=p to j- do
begin
if cur and = then
begin
k1:=getf(a[i].x);
k2:=getf(a[i].y);
if k1<>k2 then
begin
fa[k1]:=k2;
inc(tot);
res:=res+a[i].w;
end;
end;
cur:=cur shr ;
end;
for i:= to m do
begin
if a[i].w=a[j-].w then continue;
k1:=getf(a[i].x);
k2:=getf(a[i].y);
if k1<>k2 then
begin
fa[k1]:=k2;
inc(tot);
res:=res+a[i].w;
end;
end;
if (res=sum) and (tot=n-) then exit() else exit();
end; begin
readln(n,m);
for i:= to m do
readln(a[i].x,a[i].y,a[i].w);
sort(,m);
for i:= to n do
fa[i]:=i;
rank[]:=;
p:=;
for i:= to m do
begin
if a[i].w<>a[i-].w then inc(p);
rank[i]:=p;
end;
i:=;
j:=;
while i<n- do
begin
inc(j);
k1:=getf(a[j].x);
k2:=getf(a[j].y);
if k1<>k2 then
begin
fa[k1]:=k2;
inc(i);
inc(v[rank[j]]);
sum:=sum+a[j].w;
end;
end;
if i<n- then
begin
writeln();
halt;
end;
ans:=;
i:=;
while i<=m do
begin
j:=i+;
while a[i].w=a[j].w do inc(j);
if v[rank[i]]> then
begin
s:=;
for k:= to shl (j-i)- do
if calc(k)=v[rank[i]] then s:=s+check(i,k);
ans:=ans*s mod mo;
end;
i:=j;
end;
writeln(ans);
end.