Minimum Total Travel Cost

You are given a network of N cities and M bidirectional roads connecting them. Each road has an associated travel cost. Your task is to compute the minimum total travel cost needed to connect all cities so that every city is reachable from any other city. If it is impossible to connect all cities, output -1.

This problem can be modeled as finding the Minimum Spanning Tree (MST) of the graph. Recall that a spanning tree connects all nodes in a graph with exactly N-1 edges. If such a tree exists, its total edge weight is the answer.

Note: If there is only one city, the travel cost is 0. If there are no roads but more than one city, the output should be -1.

inputFormat

The input is given from standard input and has the following format:

N M
u1 v1 w1
u2 v2 w2
... 

Here, the first line contains two integers N (the number of cities) and M (the number of roads). Each of the next M lines contains three integers u, v and w, representing a road connecting city u and city v with a travel cost of w.

outputFormat

Output a single integer to standard output: the minimum total travel cost required to connect all cities. If it is not possible to connect all cities, output -1.

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

10