Count of Distinct Minimum Spanning Trees

You are given a simple undirected weighted graph. Instead of simply computing its minimum spanning tree (MST), you are required to determine the number of different MSTs in the graph. Two MSTs are considered different if they differ in at least one edge.

Since the number of MSTs might be very large, output the result modulo \(31011\).

Note: The graph vertices are numbered from 1 to \(n\). If the graph is not connected (i.e. an MST does not exist), output 0.

Hint: You may first run a standard MST algorithm (e.g. Kruskal's algorithm) and then, for each group of edges with the same weight which are candidates for inclusion in the MST, count the number of ways to choose the necessary edges. For a small number of vertices in each group, you can use brute force (by iterating through all subsets) to count the spanning trees in that subgraph.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m \leq \text{small})\), denoting the number of vertices and edges, respectively.

Each of the next \(m\) lines contains three integers \(u\), \(v\) and \(w\), representing an undirected edge between vertices \(u\) and \(v\) with weight \(w\).

outputFormat

Output a single integer: the number of distinct minimum spanning trees modulo \(31011\). If an MST does not exist (the graph is disconnected), output 0.

sample

3 3
1 2 1
2 3 1
1 3 1

3