Minimum Cost to Connect All Cities

You are given a kingdom with n cities and m possible bidirectional roads connecting them. Each road connects two different cities and has an associated cost. Your task is to choose a subset of these roads such that all the cities are connected (i.e. the graph is a spanning tree) and the total cost is minimized.

The problem can be formulated as finding a minimum spanning tree for a graph. In theory, if the graph is connected, there exists a spanning tree with n - 1 edges. Otherwise, if the graph is disconnected, it is impossible to connect all cities and the answer is -1.

You may use the following formula if needed: A spanning tree has exactly \(n-1\) edges.

Input/Output: Your solution must read from standard input and write to standard output.

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 cities and the number of roads respectively. Each of the following m lines contains three integers a, b, and c, representing a road that connects city a with city b with cost c (the cities are numbered from 1 to n).

outputFormat

Output a single integer representing the minimum total cost to connect all cities. Output -1 if it is impossible to connect all cities.

4 5
1 2 3
2 3 4
3 4 5
1 3 6
1 4 7

12