Minimum Cost to Connect All Nodes

You are given an undirected graph with n nodes (numbered from 1 to n) and m edges. Each edge has an associated weight. Your task is to determine the minimum cost required to connect all the nodes, i.e. to form a spanning tree. Note that in a connected graph, a spanning tree has exactly \(n-1\) edges.

If it is not possible to connect all the nodes (i.e. the graph is disconnected), output -1. The solution can be found by using a minimum spanning tree algorithm such as Kruskal's algorithm with a union-find data structure.

inputFormat

The first line of the input contains 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.

Input is given from standard input (stdin).

outputFormat

Output a single integer. This integer is the minimum cost to connect all nodes, or -1 if it is not possible. The answer should be printed to standard output (stdout).

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

5