Minimum Cost to Connect Islands

You are given a collection of islands and a list of potential bridges connecting pairs of islands with an associated cost. Your task is to determine the minimum cost required to connect all the islands so that there exists a path between any two islands. If it is impossible to connect all islands, return -1.

The problem can be modeled as finding a Minimum Spanning Tree (MST) of a graph. One effective method to solve this is by using Kruskal's algorithm along with the union-find (disjoint set) data structure. Use union by rank and path compression optimizations where possible to ensure efficiency for larger inputs.

Hint: Two important functions in the union-find structure are:
$$\texttt{find(parent, i)}$$ which returns the representative of the set that element (i) belongs to, and
$$\texttt{union(parent, rank, x, y)}$$ which unites two sets whose representatives are (x) and (y).

inputFormat

The input starts with a single integer (T) representing the number of test cases. For each test case, the first line contains two space-separated integers (n) and (m), where (n) is the number of islands and (m) is the number of bridges. This is followed by (m) lines, each containing three space-separated integers (u), (v), and (w) that indicate a bridge connecting island (u) and island (v) with a cost (w). All input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing the minimum cost required to connect all islands. If it is impossible to connect all islands, print (-1). All output should be written to standard output (stdout).## sample

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

7
-1