Minimum Total Travel Time

You are given a network of houses connected by bidirectional roads. Each road has an associated travel time. Amy, the postal worker, needs to deliver mail to all houses while spending the minimum total travel time. In order to achieve this, she must pick a set of roads that connects all houses with the minimum total travel time. This is equivalent to finding the Minimum Spanning Tree (MST) of the graph.

The input consists of the number of houses and roads followed by the details of each road. Each road is specified by two endpoints and the travel time between them. Your task is to compute and output the total travel time of the MST, which represents the minimum total travel time required to deliver the mail.

Note: All formulas are given in LaTeX format. For example, the sum of the weights in the MST is represented as: $$\min \sum_{e \in MST} w_e.$$

inputFormat

The first line of input contains two integers \(n\) and \(m\) where \(n\) is the number of houses and \(m\) is the number of roads. Each of the following \(m\) lines contains three integers \(A\), \(B\), and \(T\), indicating that there is a road between house \(A\) and house \(B\) with a travel time of \(T\).

outputFormat

Output a single integer representing the minimum total travel time required to deliver the mail, which is the total weight of the Minimum Spanning Tree (MST) of the given graph.

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

10