Minimum Fiber Optic Installation

Farmer John (FJ) has installed a high-speed network line at his farm and now wishes to share this connection with other farms. To minimize costs, he wants to lay down the shortest possible fiber optic cable to connect all the farms.

You are given a list of connection costs between different farms. Your task is to determine the minimum total length of fiber needed to connect all the farms. The distance (cost) for every pair of farms does not exceed \(10^5\).

This is a classic Minimum Spanning Tree problem. Use algorithms such as Kruskal's or Prim's to compute the answer.

inputFormat

The input begins with two integers \(n\) and \(m\) separated by a space, where \(n\) is the number of farms (vertices) and \(m\) is the number of possible connections (edges).

Then \(m\) lines follow, each containing three integers \(u\), \(v\) and \(w\), representing a connection between farm \(u\) and farm \(v\) with a cost of \(w\).

You may assume that the given graph is connected.

outputFormat

Output a single integer representing the minimum total cost to connect all the farms.

sample

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

13