Minimum Railway Construction Cost

You are given a set of cities and possible roads connecting some pairs of cities, where each road has an associated construction cost. Your task is to determine the minimum cost required to construct a railway network that connects all the cities. If it is impossible to connect all cities with the given roads, output -1.

The problem can be formulated in terms of finding a Minimum Spanning Tree (MST) in a weighted undirected graph. That is, given ( n ) cities and ( m ) roads represented by triples ( (u, v, w) ), where ( u ) and ( v ) are the city indices and ( w ) is the cost, you need to calculate the sum of the weights of the MST. Use standard algorithms like Kruskal's or Prim's algorithm to solve the problem.

inputFormat

The input is read from standard input and consists of multiple lines. The first line contains two integers ( n ) and ( m ), representing the number of cities and the number of roads respectively. The next ( m ) lines each contain three integers ( u ), ( v ), and ( w ), indicating that there is a road connecting city ( u ) and city ( v ) with a construction cost of ( w ).

outputFormat

Output a single integer representing the minimum total construction cost required to connect all the cities. If it is not possible to connect all the cities, output -1.## sample

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

6