Minimum Spanning Tree

Given an undirected graph with n vertices and m edges, your task is to compute the minimum cost required to connect all vertices. The graph is described by m edges; each edge connects two vertices with an associated positive weight. If it is impossible to connect all vertices (i.e. the graph is disconnected), output \(-1\).

You may use Kruskal's algorithm or any other efficient method. The minimum spanning tree (MST) is defined as the tree that connects all vertices with the minimum possible total weight:

\(\min \sum_{(u,v) \in \text{MST}} w(u,v)\)

The input is read from stdin and the output should be written to stdout.

inputFormat

The first line of input contains two integers n and m, representing the number of vertices and edges respectively. Each of the next m lines contains three integers u, v, and w indicating that there is an undirected edge between vertex u and vertex v with weight w.

outputFormat

Output a single integer representing the total weight of the minimum spanning tree if all vertices can be connected, or \(-1\) if it is impossible.

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

6