Description

You are given a simple undirected weighted graph. You are not satisfied with finding just one minimum spanning tree (MST); instead, you want to know how many different MSTs the graph has. Two MSTs are considered different if they differ by at least one edge. Since the number of different MSTs can be large, you only need to output the count modulo $31011$.

Input Format

The first line contains two integers $n$ and $m$, where $1 \le n \le 100$, $1 \le m \le 1000$, representing the number of nodes and edges of the undirected graph. Nodes are numbered from $1$ to $n$.

The next $m$ lines each contain three integers $a, b, c$, indicating that there is an edge between nodes $a$ and $b$ with weight $c$, where $1 \le c \le 10^9$.

It is guaranteed that there are no self-loops or multiple edges. Note: For any fixed weight, there are at most $10$ edges with that weight.

Output Format

Output the number of different minimum spanning trees. You only need to output the count modulo $31011$.

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

8

Hint

Constraints and Conventions

For all testdata, $1 \le n \le 100$, $1 \le m \le 1000$, $1 \le c_i \le 10^9$.

Translated by ChatGPT 5