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