David's Magic Band Network

Submit solution

Points: 2
Time limit: 1.0s
Memory limit: 512M

Problem type

David is not only an avid collector of arrays and sloths but is also a keen musician and as such is the chief administrator of the National Band Network or NBN. The NBN connects band members together with bi-directional links where connections bear a cost \(c_{ij}\) to maintain. Given a description of the current NBN, write David a program that tells him the minimum total cost of all connections needed to keep any previously connected members connected.

Input Specification

The first line contains two integers \(m, c\) \((1 \leq m \leq 10^6),(1 \leq c \leq m(m-1)/2 \leq 10^6)\), the number of members and connections respectively.

The following \(c\) lines contain three integers, \(i,j,c_{ij}\) \((1 \leq i,j \leq v)(1 \leq c_{ij} \leq 10^5)\) denoting a bi-directional connection from \(i\) to \(j\) with cost \(c_{ij}\).

Note: you are guaranteed that all \(m\) members are connected somehow.

Output Specification

A single integer representing the minimum total cost of all connections needed to maintain connectivity between members. There will be no self-connecting edges.

Sample Input 1

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

Sample Output 1


Sample Input 2

4 6
1 2 1
1 4 3
2 3 1
1 3 4
2 4 2
3 4 1

Sample Output 2



There are no comments at the moment.