Description
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。
Input
第一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,000。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。
Output
输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。
Sample Input
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
Sample Output
8
网上的题解基本上没有证明（或许有，但是我没看见，然后懒得找了）
两个最小生成树的权值相同的边作用相同（连通情况）
我们可以用反证法
假设有两个最小生成树的权值相同的边作用不同，那么把最小的作用不同的权值找出来
然后我们把他们的连通情况合并（去环），需要的边肯定会变多，而且一定可以做到，相当于我们用多出来的边代替了权值比它大的边，那这与前面说的这是最小生成树矛盾
例：假设权值为1的边在一棵最小生成树里造成连通情况是（1,2）（3,4），在另一棵最小生成树里造成的连通情况是（1,4）（2,3）
那我们可以合并它们用权值为1的边做到（1,2,3,4）,来替换一条权值大于1的边，得到一颗权值更小的树
证毕.
所以我们记录每种权值的边所造成的连通情况记录下来，每个权值做一遍，乘起来就是答案（注意判断无解的情况）
const
maxn=;
maxm=;
h=;
var
ans,n,m,l:longint;
u,v,w:array[..maxm]of longint;
a:array[..,..]of longint; procedure swap(var x,y:longint);
var
t:longint;
begin
t:=x;x:=y;y:=t;
end; procedure sort(l,r:longint);
var
i,j,y:longint;
begin
i:=l;
j:=r;
y:=w[(l+r)>>];
repeat
while w[i]<y do
inc(i);
while w[j]>y do
dec(j);
if i<=j then
begin
swap(u[i],u[j]);
swap(v[i],v[j]);
swap(w[i],w[j]);
inc(i);
dec(j);
end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end; function bit(x:longint):longint;
begin
if x= then exit();
exit(bit(x-(x and -x))+);
end; procedure init;
var
i,k:longint;
begin
read(n,m);
for i:= to m do
read(u[i],v[i],w[i]);
sort(,m);
for i:= to do
begin
k:=bit(i);
inc(a[k,]);
a[k,a[k,]]:=i;
end;
end; var
f,f2,vis:array[..maxn]of longint;
xu:array[..maxm]of longint;
time:longint; function find(x:longint):longint;
begin
if vis[x]<>time then
begin
f[x]:=f2[x];
vis[x]:=time;
end;
if f[x]=x then exit(x);
f[x]:=find(f[x]);
exit(f[x]);
end; function find2(x:longint):longint;
begin
if f2[x]=x then exit(x);
f2[x]:=find2(f2[x]);
exit(f2[x]);
end; function flag(x:longint):boolean;
var
i:longint;
begin
i:=;
while x> do
begin
inc(i);
if x and = then
begin
if find(u[l+i])=find(v[l+i]) then exit(false);
if (f[u[l+i]]<>f[v[l+i]])and(find2(u[l+i])=find2(v[l+i])) then exit(false);
f[f[u[l+i]]]:=f[v[l+i]];
end;
x:=x>>;
end;
exit(true);
end; procedure work;
var
i,j,s,last:longint;
begin
ans:=;
for i:= to n do
f2[i]:=i;
for i:= to m do
begin
if w[i]=w[i-] then xu[i]:=xu[i-];
if find2(u[i])<>find2(v[i]) then
begin
inc(xu[i]);
f2[f2[u[i]]]:=f2[v[i]];
end;
end;
for i:= to n- do
if find2(i)<>find2(i+) then ans:=;
for i:= to n do
f2[i]:=i;
l:=;
last:=;
for i:= to m do
if w[i]<>w[i+] then
begin
s:=;
while last<l do
begin
inc(last);
f2[find2(u[last])]:=find2(v[last]);
end;
for j:= to a[xu[i],] do
begin
if a[xu[i],j]>=<<(i-l) then break;
inc(time);
if flag(a[xu[i],j]) then inc(s);
end;
l:=i;
ans:=ans*s mod h;
end;
write(ans);
end; begin
init;
work;
end.