Description
The description provided for this problem:
Agent Ω tracked a set of swarms to Demos, one of Mars’ moons, where they bombarded the surface. Upon more investigation, she discovered that they had collapsed one of C.H.I.M.E.R.A.’s underground warehouse complexes with a single entrence. Clearly there must be information there that the Lion does not want people to know about.
Given a graph of the warehouse complex where vertices represent storage rooms and edges indicate the tunnels connecting those storage rooms (along with a value representing the effort needed to clear that tunnel), determine the LEAST total effort that can be used to clear a subset of the tunnels such that all of the storage rooms will again be connected.
Input Format
The first line contains N, the number of storage rooms, and M, the number of hallways.
The next M lines each have three integer values. The first two identify the storage rooms involved, while the third provides the effort to clear the tunnel.
All graphs are gauranteed to be connected.
Constraints
1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
0 ≤ efforst costs ≤ 1,000,000
0 ≤ storage room IDs < N
Output Format
A single value indicating the minimum total effort to clear enough tunnels to connect the storage rooms.
Example 0
Sample Input
5 6
0 1 5
0 2 10
0 3 2
1 3 3
1 4 8
3 4 1
Sample Output
16
