Minimum Bicycle Lane Length

You are given a network of huts connected by paths. Each path has an associated length. Your task is to determine the minimum total length required to connect all huts, forming a network that allows travel between any two huts.

This problem is equivalent to finding the Minimum Spanning Tree (MST) of a weighted graph. Mathematically, if \(E'\) is the set of edges in the MST, then the total cost is \(\sum_{e \in E'} w(e)\), where \(w(e)\) is the weight (length) of edge \(e\). Common algorithms to solve this problem include Prim's algorithm and Kruskal's algorithm.

In this problem, you are required to implement a solution that reads input from standard input and writes the answer (the minimum total length) to standard output.

inputFormat

The input starts with two integers \(n\) and \(m\) where \(n\) is the number of huts and \(m\) is the number of paths. Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\), indicating there is a bidirectional path between hut \(u\) and hut \(v\) with a length of \(w\).

outputFormat

Output a single integer representing the minimum total length required to connect all the huts.

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

12