All problems

Compulsory Cable

Hard · minimum spanning tree

A telecom firm has n exchanges, numbered 0 to n - 1. The list cables holds every cable it could use: each entry [a, b, cost] is a two-way cable between exchanges a and b that costs cost to lay. The cable at position i is called cable i, counting from 0.

A network is any set of cables that lets every exchange reach every other, directly or through other exchanges. Its cost is the total cost of its cables.

The regulator is about to name one cable that must be part of the network, but has not said which. For every cable i, work out the cost of the cheapest network that includes cable i.

Return a list with one number per cable, in the same order as cables: the cheapest network cost when cable i is compulsory.

The cables connect all the exchanges, so a network always exists. Several cables may join the same pair of exchanges, and costs may be 0.

Examples

Example 1

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

Output: [6, 6, 6, 8, 8]

The cheapest network uses the first three cables and costs 6. Forcing cable 3 (0-2, cost 4) means dropping cable 1 (cost 2): 6 - 2 + 4 = 8. Forcing cable 4 (1-3, cost 5) means dropping cable 2 (cost 3): 6 - 3 + 5 = 8.

Example 2

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

Output: [5, 2]

Either cable alone joins the two exchanges, so the cost is just that cable's cost.

Example 3

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

Output: [8, 8, 8]

Any two of the three cables make a network costing 8, so whichever cable is forced, the answer is 8.

Constraints