Heritage Bridges

Medium · minimum spanning tree

An archipelago has n islands, numbered 0 to n - 1. The council wants every island to be reachable from every other island, directly or through other islands, by bridges.

The list bridges holds the bridges that could be built. Each entry is [a, b, cost, must]: a bridge between islands a and b, usable in both directions, that costs cost to build.

If must is 1, the bridge is protected by a heritage order. It has to be built, and its cost is always paid, even if the islands it joins are already connected in some other way.
If must is 0, the bridge is optional. Build it or leave it out.

Return the smallest total cost of a set of bridges that includes every protected bridge and connects all the islands. If there is no such set, return -1. If nothing needs building at all, the answer is 0.

Several bridges may join the same pair of islands.

Examples

Example 1

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

Output: 9

The protected bridge costs 5. Adding the optional bridges of cost 1 and 3 joins all four islands.

Example 2

Input: n = 3, bridges = [[0, 1, 2, 1], [1, 2, 2, 1], [0, 2, 2, 1], [0, 1, 1, 0]]

Output: 6

All three protected bridges must be built and paid for, even though two of them already connect everything.

Example 3

Input: n = 3, bridges = [[0, 1, 1, 0]]

Output: -1

No bridge reaches island 2, so the islands cannot be connected.

Constraints

1 <= n <= 1000
0 <= len(bridges) <= 5000
Each bridge is [a, b, cost, must] with 0 <= a, b < n, a != b, 1 <= cost <= 10^4 and must equal 0 or 1.