Minimum Road Decoration

You are given a set of test cases. For each test case, you have a number of houses and a list of roads connecting these houses. Every road is associated with a length, representing the cost to decorate it.

Your task is to choose a subset of these roads such that all houses become connected while the total length (or cost) is minimized. This is equivalent to finding the Minimum Spanning Tree (MST) of the graph formed by the houses and roads.

The MST problem can be solved using algorithms like Kruskal's or Prim's. In this problem, you are encouraged to implement any efficient method to compute the MST.

If there are no roads or only a single house, the output should be 0.

Note: Use stdin for input and stdout for output.

inputFormat

The input starts with an integer T, representing the number of test cases. Each test case consists of:

• A line containing two integers N and M, where N is the number of houses and M is the number of roads.
• M lines each containing three integers u, v, and w, denoting a road between houses u and v with length w.

All input should be read from standard input (stdin).

outputFormat

For each test case, output a single integer on a new line representing the minimum total length of the roads that need to be decorated, which is equivalent to the weight of the minimum spanning tree. The output should be written to standard output (stdout).## sample

1
4 5
1 2 3
2 3 4
3 4 5
4 1 2
1 3 7

9