407362: GYM102770 J Just an Old Problem

Chenjb came across a tricky problem in the 2018 ICPC Asia Xuzhou Regional Contest, which was a problem about the minimum spanning tree (MST).

A minimum spanning tree, or minimum weight spanning tree, is a subset of edges from an edge-weighted undirected graph, which forms a tree with the minimum possible total edge weight that connects all the vertices together.

In that problem, Chenjb was required to calculate the summation of total edge weights of all MSTs for a given graph, which obviously equals to the product of the total edge weight in an MST and the total number of different MSTs. Note that two spanning trees are different if and only if their edge sets are different.

It took Chenjb about an hour to solve that problem using Kruskal and Matrix-tree Theorem. Now Chenjb believes that you can solve it faster than him. You will be given a connected undirected graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges, the vertices of which are labelled by $$$1,2,\dots,n$$$. Interestingly, there are no simple paths passing through $$$8$$$ vertices in $$$G$$$. You need to calculate the summation of total edge weights of all MSTs for the given graph. To decrease the size of the output, you only need to output the answer modulo $$$2^{30}$$$.

The input contains multiple cases. The first line of the input contains a single integer $$$T$$$ ($$$1 \leq T \leq 5\,000$$$), the number of cases.

For each case, the first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 50\,000$$$, $$$1\leq m\leq 100\,000$$$), denoting the number of vertices and the number of edges in the graph.

For the next $$$m$$$ lines, the $$$i$$$-th line contains three integers $$$u_i,v_i$$$ and $$$w_i$$$ ($$$1\le i \le m, 1 \leq u_i,v_i\leq n$$$, $$$u_i\neq v_i$$$, $$$1\leq w_i\leq 10\,000$$$), denoting a bidirectional edge connecting the $$$u_i$$$-th vertex and the $$$v_i$$$-th vertex with weight $$$w_i$$$. It is guaranteed that there won't be multiple edges between the same pair of vertices, and it is also guaranteed that it is impossible to find any simple path passing through $$$8$$$ vertices.

It is guaranteed that the sum of $$$n$$$ over all cases does not exceed $$$50\,000$$$, and the sum of $$$m$$$ over all cases does not exceed $$$100\,000$$$.

For each case, print a single line containing a single integer, denoting the answer modulo $$$2^{30}$$$.

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

9
24