Minimum Cost to Connect Cities

Given n cities and m possible roads connecting them, where each road is represented as (u, v, w) indicating a road between city u and city v with cost w, your task is to compute the minimum cost required to connect all the cities. Use Kruskal's algorithm to construct a Minimum Spanning Tree (MST). If it is impossible to connect all cities, output \(-1\).

Note: The cities are labeled from \(1\) to \(n\), and if \(n = 1\), the MST cost is \(0\).

inputFormat

The input is read from standard input (stdin). The first line contains two integers (n) and (m), denoting the number of cities and the number of roads. Each of the following (m) lines contains three integers (u), (v), and (w), representing a road between cities (u) and (v) with cost (w).

outputFormat

Output a single integer to standard output (stdout) which is the minimum cost required to connect all the cities. If it is not possible to connect all the cities, output (-1).## sample

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

6