SP2670 MSTS - Count Minimum Spanning Trees

Your task is simple in this problem: count the number of **minimum spanning tree** ([Wikipedia](http://en.wikipedia.org/wiki/Minimum_spanning_tree)) 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.

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.

Print the **answer** % 31011.