Minimum Travel Cost

The kingdom consists of n cities connected by m bidirectional roads. Each road connects two different cities and has an associated cost. The king wishes to travel between all cities by selecting a subset of roads such that every pair of cities is connected, while minimizing the total travel cost.

If it is not possible to connect all the cities, output -1.

This problem can be solved using the Minimum Spanning Tree (MST) algorithm. The total cost of the MST is given by:

\( \text{MST Cost} = \sum_{e \in E'} w_e \),

where \( E' \) is the set of selected roads and \( w_e \) is the cost of road \( e \). In case the graph is disconnected, no MST exists and the answer is -1.

inputFormat

The first line of input contains two integers n and m separated by a space, representing the number of cities and the number of roads, respectively.

This is followed by m lines, each containing three integers u, v and w, where u and v are the cities connected by a road, and w is the travel cost on that road.

outputFormat

Output a single integer representing the minimum travel cost to connect all the cities. If it is impossible to connect all cities, output -1.

4 5
1 2 5
1 3 10
2 3 3
2 4 8
3 4 4

12