Minimum Cost to Connect Cities

You are given a network of n cities and m potential roads. Each road connects two cities and has an associated length (cost). Your task is to determine the minimum total cost to connect all the cities using exactly n - 1 roads, i.e. constructing a Minimum Spanning Tree (MST). If it is impossible to connect all cities, output -1.

Note: If there is only one city and no road is given, the connection cost is 0. However, if any road is provided for a single city, output -1 as it is considered invalid.

The formula for the number of roads required is given by: $$m \geq n - 1$$.

inputFormat

The first line contains two integers n and m separated by a space, where n is the number of cities and m is the number of potential roads.

Each of the following m lines contains three integers u, v, and w, which represent a road between city u and city v with cost w.

outputFormat

Output a single integer which is the minimum total cost required to connect all cities using exactly n - 1 roads, or -1 if it is impossible.

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

6