Minimum Spanning Tree Expedition

In a country with n cities and m bidirectional flights, each flight connects two cities with a known cost. Your mission is to select a subset of these flights such that any city is reachable from any other city (directly or indirectly) while minimizing the total cost.

This is a classic Minimum Spanning Tree problem. Formally, given a connected graph \(G=(V,E)\) with a weight function \(w: E \to \mathbb{R}\), find a spanning tree \(T\subseteq E\) such that the total cost \[ \sum_{e \in T} w(e) \] is minimized. If it is impossible to connect all cities, output -1.

inputFormat

The first line contains two integers n and m (≥ 1), where n is the number of cities and m is the number of flights.

Each of the following m lines contains three integers u, v, and w, indicating a bidirectional flight between cities u and v with cost w.

Cities are numbered from 1 to n.

outputFormat

Output a single integer as the minimum total cost to connect all the cities. If it is impossible to connect every pair of cities, print -1.

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

11