Minimum Bridge Connection Cost

You are given n islands and a list of potential bridges connecting pairs of islands. Each bridge has an associated cost. Your task is to compute the minimum total cost required to connect the islands within each connected component. In other words, for each connected component, you need to compute the cost of the minimum spanning tree (MST) and output the sum of these costs.

The MST cost for a connected component is defined as $$\text{MST cost} = \sum_{e \in T} \text{weight}(e),$$ where \(T\) is the set of edges in the MST. If an island is isolated (i.e., no bridges), then its cost is 0.

If there are multiple components, simply output the sum of the MST costs for all components.

inputFormat

The input is read from stdin and has the following format:

n
m
u1 v1 w1
u2 v2 w2
... 
um vm wm

Where:

• n is the number of islands (numbered from 0 to n-1).
• m is the number of potential bridges.
• Each of the next m lines contains three integers ui, vi, and wi, representing a bridge between island ui and island vi with cost wi.

outputFormat

The output is a single integer written to stdout representing the sum of the minimum spanning tree (or forest) costs over all connected components.

4
5
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4

19