Taco's Minimum Spanning Tree

This problem involves finding the minimum cost to connect all cities using a set of roads. You are given a graph with \(n\) cities and \(m\) roads. Each road is described by two cities \(u\) and \(v\) and a cost \(c\). Your task is to use Kruskal's algorithm to find the Minimum Spanning Tree (MST) of the graph. If it is not possible to connect all the cities (i.e. the graph is disconnected), output \(-1\).

The MST is defined as a subset of the roads that connects all cities with the minimum total cost and has exactly \(n-1\) edges. Use union-find (disjoint set union) to manage connectivity while selecting edges.

inputFormat

The input is read from standard input (stdin) and is in the following format:

n m
u1 v1 c1
u2 v2 c2
... 
um vm cm

Here, the first line contains two integers \(n\) (the number of cities) and \(m\) (the number of roads). Each of the next \(m\) lines contains three integers \(u\), \(v\) and \(c\), representing a bidirectional road between city \(u\) and city \(v\) with cost \(c\).

outputFormat

Output a single integer to standard output (stdout): the total cost of the minimum spanning tree if the graph is connected, or \(-1\) if it is not possible to connect all cities.

## sample

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

4

</p>