Constructing a Minimum Spanning Tree

You are given an undirected weighted graph. Your task is to construct a Minimum Spanning Tree (MST) using (\text{Kruskal's algorithm}) and compute the total weight of the MST. An MST of a connected graph (G = (V, E)) is a subset of the edges that connects all vertices together, without any cycles, and with the minimum possible total edge weight. You can assume that the input graph is always connected, i.e. there is at least one way to connect all vertices.

inputFormat

The input is given via standard input (stdin). The first line contains an integer (T) denoting the number of test cases. Each test case begins with a line containing two integers (N) and (M), where (N) is the number of nodes and (M) is the number of edges. The following (M) lines each contain 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 line containing a single integer: the total weight of the Minimum Spanning Tree for that test case.## sample

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

6
3