Minimum Spanning Tree for Road Construction

In this problem, you are given an undirected weighted graph representing a network of roads between cities. The graph contains ( n ) vertices (cities) and ( m ) edges (roads). Each edge is described by three integers ( u ), ( v ), and ( w ), where ( w ) is the length of the road. Your task is to compute the total weight of the minimum spanning tree (MST) of the graph. In other words, choose a subset of the roads such that all cities are connected and the sum of the road lengths is minimized.

The minimum spanning tree can be computed using well known algorithms such as Kruskal's or Prim's algorithm. For an edge with weight ( w ), the contribution to the MST is determined by the connectivity of the graph. Formally, if ( E' ) is the set of edges chosen, then you need to minimize ( \sum_{e \in E'} w_e ) under the constraint that the graph ( (V, E') ) is connected and acyclic.

inputFormat

The input is given via standard input. The first line contains a single integer ( T ) representing the number of test cases. Each test case starts with a line containing two integers ( n ) and ( m ) (number of nodes and number of edges). This is followed by ( m ) lines, each containing three integers ( u ), ( v ), and ( w ), denoting an edge between nodes ( u ) and ( v ) with weight ( w ). It is guaranteed that the graph is connected.

outputFormat

For each test case, output a single line with one integer: the total weight of the minimum spanning tree of the graph. The output should be written to standard output.## sample

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

12
3
3