SUSTech Online Judge

Problem I: Sum of value

Time Limit: 2 Sec Memory Limit: 128 MB
Submit: 201 Solved: 22
[Submit][Status][Web Board]

Description

Grace has a connected graph of n nodes and m undirected edges. These nodes are numbered from 1 to n. Each edge has a value. The graph does not contain self-loop and there is at most one edge between any two nodes. Addtionally, there are at most two non-intersect paths, which shares no common edges, between any two nodes. She defines W(x,y) as the minimum cost to let no path between x and y. The cost to cut one edge is the value of the edge, and once you cut an edge, the edge disappears in the graph. Every time you need to calculate the minimum cost of a pair, you need to cut the edges from the original graph. every W is independent. At last, Grace asks you to calculate this

sum of W(i,j)(i != j)

Input

The first line will be an integer T

, which is the number of the test cases(1 <= T <= 10)

. For each test case, the first line will be three integers n

, m(1 <= n <= 10⁵, 1 <= m <= 1.5*(n - 1))

. Then followed by m

lines, each line will be three integers x

, y

and z(1 <= z <= 10⁹)

, it means that there is an undirected edge between x

and y

whose value is z

Output

For each test output the answer for the query in one line.

Sample Input

Sample Output

HINT

[Submit][Status]