Minimum Road Length

You are given an undirected weighted graph representing a network of cities and roads. The graph is defined by n nodes and m edges. Each edge is described by three integers: the endpoints u and v (0-indexed) and the weight w, which represents the length of the road connecting the two cities.

Your task is to choose a subset of these roads so that the entire network remains connected while minimizing the total road length. This is equivalent to finding the Minimum Spanning Tree (MST) of the graph. Formally, if MST is the set of edges selected, you need to compute:

$$ \min \sum_{(u,v) \in MST} w(u,v) $$

You are required to process multiple test cases.

inputFormat

The input is given via standard input (stdin) and follows the format below:

T
n1 m1
u1 v1 w1
u2 v2 w2
... (m1 edges)
n2 m2
u1 v1 w1
... (m2 edges)
... (T test cases)

Where:

• T is the number of test cases.
• For each test case, the first line contains two integers n (number of nodes) and m (number of edges).
• Each of the next m lines contains three integers u, v and w, representing an edge between nodes u and v with weight w.

outputFormat

For each test case, output a single integer representing the total length of the Minimum Spanning Tree (MST) of the graph. The results for each test case should be printed on their own line (via stdout).

## sample

2
4 5
0 1 3
0 2 2
0 3 4
1 2 5
2 3 4
5 7
0 1 1
0 2 4
0 3 3
1 2 2
1 4 6
2 3 5
3 4 7

9
12

</p>