## 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.

### Example

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

Output:
8
``` 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.