Minimum Cost to Connect Warehouses

You are given a set of (n) warehouses and (m) bidirectional routes connecting them. Each route connects two warehouses and has an associated transportation cost. Your task is to determine the minimum cost required to connect all the warehouses so that any warehouse is reachable from any other warehouse directly or indirectly. If it is not possible to connect all warehouses, output -1.

This problem essentially asks you to construct a minimum spanning tree (MST) of the graph. The total cost is the sum of the costs of the selected routes: [ C = \sum_{e \in T} c(e) ] where (T) is the set of routes included in the MST and (c(e)) is the cost of route (e).

inputFormat

The first line contains two integers (n) and (m): the number of warehouses and the number of routes respectively. Each of the next (m) lines contains three integers (u), (v), and (c) indicating there is a bidirectional route between warehouse (u) and warehouse (v) with cost (c).

outputFormat

Print a single integer representing the minimum cost required to connect all warehouses. If it is not possible to connect all the warehouses, print -1.## sample

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

8