Minimal Connection Network

You are given an undirected, weighted graph. Your task is to compute the minimum total weight required to connect all the nodes, i.e., the weight of the Minimum Spanning Tree (MST). In each test case, you are provided with the number of nodes and edges, followed by the list of edges. Use Kruskal's algorithm (or any other appropriate algorithm) to compute the MST. Note that the weight of the MST is given by the formula: $$\sum_{e \in T} w(e)$$, where \(T\) is the set of edges in the MST.

You can assume that the input graphs are connected. If the graph were disconnected, an MST would not span all vertices, but for this problem, each test case is guaranteed to be connected.

inputFormat

The input begins with an integer \(T\) representing the number of test cases. For each test case, the first line contains two integers \(N\) and \(M\), denoting the number of nodes and the number of edges, respectively. This is followed by \(M\) lines, each containing three integers \(u\), \(v\), and \(w\) which describe an edge between node \(u\) and node \(v\) with weight \(w\).

outputFormat

For each test case, output a single line containing the minimum total weight required to connect all nodes (i.e., the weight of the MST).

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

6