For a graph with $n$ vertices and $m$ edges, count the number of distinct minimum spanning trees in this graph. Two spanning trees are considered different if there exists an edge in one tree that does not exist in the other.
### Input
- The first line consists of two integers $n, m$.
- The next $m$ lines, each containing three integers $u, v, w$ representing an edge of weight $w$ between $u$ and $v$.
### Output
- Print the number of distinct minimum spanning trees modulo $31011$.
### Constraints
- $1 \le n \le 100$.
- $1 \le m \le 1000$.
- $1 \le u, v \le n$.
- $1 \le w \le 10^9$.
- The number of edges having the same weight does not exceed $10$.
### Sample test
Input
```
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
```
Output:
```
8
```
