Unique Paths Network

Given a set of N cities and M undirected roads, each with an associated cost, your task is to choose a subset of these roads to connect all cities such that there is exactly one unique path between every pair of cities. In other words, the resulting network must form a tree, which by definition has exactly \(N-1\) edges.

The goal is to minimize the total cost of the selected roads. If it is impossible to connect all the cities in the required manner, print \(-1\).

Note: A valid tree, or spanning tree, for \(N\) nodes must have exactly \(N-1\) edges and no cycles.

inputFormat

The input is provided via standard input (stdin). The first line contains two integers \(N\) and \(M\), representing the number of cities and roads respectively. Each of the following \(M\) lines contains three space-separated integers \(u\), \(v\), and \(w\), which indicate that there is a road between cities \(u\) and \(v\) with cost \(w\).

outputFormat

Print a single integer representing the minimum total cost required to construct the network (spanning tree) with exactly one unique path between every two cities. If it is not possible to form such a spanning tree that connects all cities, print \(-1\).

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

6