Description

Original source: JSOI 2008

You are given a simple undirected weighted graph. You are not satisfied with just finding the minimum spanning tree (MST) of this graph but also want to know how many different MSTs exist. (Two MSTs are considered different if they differ by at least one edge.)

Input Format

The first line contains two integers, $n$ and $m$, representing the number of nodes and edges in the undirected graph, respectively. The nodes are labeled with integers from $1$ to $n$.
The next $m$ lines each contain three integers: $a$, $b$, and $c$, indicating that the weight of the edge between nodes $a$ and $b$ is $c$.

Output Format

Output the number of different MSTs. You only need to output the count modulo $31011$.

Sample 1

4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1

8

Data Range and Hints

For all data, $1\le n\le 100$, $1\le m\le 1000$, and $1\le c\le 10^9$.

The data guarantees that there are no self-loops or multiple edges.

Note: There will be no more than $10$ edges with the same weight.