Minimum Cost to Form a Tree

You are given an undirected weighted graph with \(N\) nodes and \(M\) edges. Your task is to choose a subset of edges such that the resulting graph is a tree. In other words, you must select \(N - 1\) edges that connect all nodes and ensure there is exactly one unique path between any pair of nodes.

The cost of the tree is the sum of the weights of its selected edges. If it is impossible to form such a tree (i.e., the graph is disconnected), output \(-1\).

This problem can be solved using concepts from Minimum Spanning Tree algorithms, such as Kruskal's algorithm (which uses Union-Find data structure) or Prim's algorithm.

inputFormat

The first line contains an integer \(T\) denoting the number of test cases. For each test case:

• The first line contains two integers \(N\) (number of nodes) and \(M\) (number of edges).
• The next \(M\) lines each contain three integers \(u\), \(v\), and \(w\), representing an undirected edge between nodes \(u\) and \(v\) with weight \(w\).

outputFormat

For each test case, output a single integer on a new line which is the minimum cost to form a spanning tree. If it is not possible to form a spanning tree, output \(-1\).

## sample

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

8

</p>