All problems

Cable Upgrade Budget

Medium · minimum spanning tree

A company runs n sites, numbered 0 to n - 1, and wants every site to be able to reach every other site over cables, directly or through other sites.

Some cables are already in the ground. The list laid holds them: each entry [a, b] is a cable between sites a and b that is already working and costs nothing to keep using.

The list cables holds the new cables you may buy. Each entry [a, b, cost] is a cable between sites a and b that costs cost to buy and install. You may buy any of them, in any combination. Every cable, laid or new, works in both directions.

Return the smallest total cost of new cables that makes all the sites connected. If no choice of new cables can connect every site, return -1. If the laid cables already connect everything, the answer is 0.

Several cables may join the same two sites, and costs may be 0.

Examples

Example 1

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

Output: 7

Sites 0 and 1 are already joined. Buy 0-2 (cost 3) and 2-3 (cost 4): 3 + 4 = 7. The cable 1-2 would cost more and is not needed.

Example 2

Input: n = 3, laid = [[0, 1], [1, 2]], cables = [[0, 2, 9]]

Output: 0

The laid cables already connect all three sites, so nothing needs to be bought.

Example 3

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

Output: -1

Site 2 has no cable to anywhere, laid or new, so it can never be connected.

Constraints