Total Travel Time of the Minimum Spanning Tree

You are given a connected undirected graph comprising n cities and m bidirectional roads. Each road connects two cities and has an associated travel time. Your task is to compute the total travel time of the Minimum Spanning Tree (MST) of the graph.

The MST is defined as a tree that connects all the vertices in the graph with the minimum possible total edge weight. In mathematical notation, given a set of edges \(E\) with weights \(w(e)\), the MST minimizes \(\sum_{e \in E'} w(e)\) where \(E'\) is the set of edges in the spanning tree.

If the graph consists of a single city, the total travel time is 0.

inputFormat

The first line of input contains two integers n and m, where n is the number of cities and m is the number of roads. Each of the next m lines contains three integers u, v, and w representing a road from city u to city v with travel time w.

outputFormat

Output a single integer representing the total travel time of the Minimum Spanning Tree of the graph. If n = 1, output 0.## sample

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

6