Minimum Total Communication Distance

You are given a network of cities and a set of possible bidirectional connections between them. Each connection has an associated distance. Your task is to determine the minimum total distance required to connect all the cities so that communication can be established between any pair of cities. If it is impossible to connect all the cities, output -1.

This problem can be solved by building a minimum spanning tree (MST) of the graph. In an undirected graph \( G = (V, E) \), an MST is a subset of the edges that connects all the vertices together, without any cycles, and with the minimum possible total edge weight. A common approach to obtain an MST is Kruskal's algorithm using union-find (disjoint set union) data structure. The MST total weight is the sum of the weights of its edges.

inputFormat

The first line contains two space-separated integers \( n \) and \( m \), where \( n \) is the number of cities and \( m \) is the number of connections.

Each of the following \( m \) lines contains three space-separated integers \( u \), \( v \), and \( w \), representing a connection between city \( u \) and city \( v \) with distance \( w \). Cities are numbered from 1 to \( n \).

outputFormat

Output a single integer: the minimum total distance required to connect all the cities. If it is impossible to connect all cities, output -1.

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

6