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 a_{i}, b_{i}, c_{i}, representing an undirected edge from node a_{i} to node b_{i}, with weight c_{i}. (1 ≤ a_{i} ≠ b_{i} ≤ N, 1 ≤ c_{i} ≤ 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:
20140126 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:
20120223 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:  20080429 
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 