Minimum Spanning Tree Cost Calculation

You are given a connected or disconnected undirected weighted graph with n nodes and m edges. Your task is to compute the total cost of the Minimum Spanning Tree (MST) that connects all nodes using the minimum total weight. If it is impossible to connect all nodes, output -1.

Recall that a spanning tree of a connected graph with n nodes has exactly \(n-1\) edges. The problem can be solved using Kruskal's algorithm with a union-find (disjoint set union) data structure.

inputFormat

The first line contains two integers n and m \( (1 \leq n \leq 10^5,\ 0 \leq m \leq 10^5) \) representing the number of nodes and the number of edges respectively.

The next m lines each contain three integers \(u, v, w\) \( (1 \leq u,v \leq n,\ 1 \leq w \leq 10^9) \), representing an undirected edge between node u and node v with weight w.

If m is 0 and n is 1, then the graph consists of a single node.

outputFormat

Output a single integer: the total cost of the Minimum Spanning Tree. If it is not possible to connect all nodes, output -1.

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

6