All problems

Spare Cables

Medium · minimum spanning tree

A lighthouse authority runs n stations, numbered 0 to n - 1, linked by cables. The list cables holds every cable: each entry [a, b, upkeep] is a two-way cable between stations a and b that costs upkeep a year to maintain.

At the moment every station can reach every other station, directly or through other stations. The authority wants to scrap cables to cut its yearly bill, but the stations must all still be able to reach each other afterwards.

Return the largest total yearly upkeep it can save by scrapping cables. If no cable can be scrapped, return 0.

Several cables may join the same pair of stations, and upkeep may be 0.

Examples

Example 1

Input: n = 4, cables = [[0, 1, 4], [1, 2, 3], [2, 3, 5], [0, 2, 6], [0, 3, 2]]

Output: 11

Keep 0-3 (2), 1-2 (3) and 0-1 (4), which still connect all four stations. Scrap the other two, which cost 5 + 6 = 11 a year.

Example 2

Input: n = 3, cables = [[0, 1, 5], [1, 2, 7]]

Output: 0

Scrapping either cable would cut a station off, so nothing can be saved.

Example 3

Input: n = 2, cables = [[0, 1, 8], [0, 1, 3], [1, 0, 5]]

Output: 13

Keep the cheapest of the three parallel cables (3) and scrap the other two: 8 + 5 = 13.

Constraints