MSTS - Count Minimum Spanning Trees


Your task is simple in this problem: count the number of minimum spanning tree (Wikipedia) in a simple undirected graph. The number of minimum spanning trees mean in how many ways you can select a subset of the edges of the graphs which forms a minimum spanning tree.

Input

The first line of input contains two integers N (1 ≤ N ≤ 100), M (1 ≤ M ≤ 1000). Nodes are labeled from 1 to N. In the following M lines, every line contains three integers ai, bi, ci, representing an undirected edge from node ai to node bi, with weight ci. (1 ≤ aibiN, 1 ≤ ci ≤ 1,000,000,000). You can assume there is at most one edge between two nodes, and the graph described by input is connected.

Output

Print the answer % 31011.

Example

Input:
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1

Output:
8

hide comments
Piyush Raman Srivastava: 2014-01-26 19:34:46

This question teaches a lot about MST, cayley's formula, kirchoff's matrix thm, laplace matrices, ... just sums up entire graph theory concepts on trees!! Phew!! ;)

Walrus: 2012-02-23 12:32:50

wasted a lot of time before noticing that 31011 is not a prime, may this be helpful to others.


Added by:Bin Jin
Date:2008-04-29
Time limit:1.333s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 CPP
Resource:Jiangsu TSC for Chinese NOI 08, day 2