Upgrading Communication Channels

The Ministry of Communications is planning an upgrade to improve the connectivity of optical communication channels. The goal is to upgrade as many channels as possible. However, among all possible sets that upgrade the maximum number of channels, the set with the minimum total cost should be chosen. Formally, if one upgrades a set of channels resulting in a total cost \(C\) and there are several sets with the maximum number of channels, you need to pick the set with the smallest \(C\).

This problem can be modeled as follows: You are given an undirected graph with \(n\) nodes and \(m\) edges. Each edge represents a communication channel with an upgrade cost \(w\). Your task is to select a subset of edges such that:

• The number of selected channels is maximized (i.e. in a connected graph, a spanning tree with \(n-1\) edges or, in general, a maximum spanning forest).
• Among all selections with the maximum number of channels, the total upgrade cost is minimized, i.e. \(\min\sum{w}\).

Hint: This is equivalent to computing a Minimum Spanning Tree (or Forest) using algorithms such as Kruskal's or Prim's algorithm.

inputFormat

The first line contains two integers \(n\) and \(m\), where \(n\) is the number of nodes and \(m\) is the number of communication channels.

Each of the following \(m\) lines contains three integers \(u\), \(v\) and \(w\) where \(u\) and \(v\) represent the nodes connected by the channel and \(w\) represents the cost to upgrade that channel.

outputFormat

Output a single integer, the minimum total upgrade cost when selecting the maximum number of channels (i.e. the sum of weights in the Minimum Spanning Tree or Forest).

sample

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

6