#239HardGraphs· Dijkstra with Two Distances per Node

Second Cheapest Route

A delivery company has `n` depots numbered `0` to `n - 1` joined by two-way roads. Road `[u, v, w]` connects depots `u` and `v` and costs `w` in fuel to drive in either direction. A route is a **walk**: a sequence of roads that starts at depot 0 and ends at depot `n - 1`, and roads or depots may be used more than once. The cheapest route is used for regular deliveries. For emergencies the dispatcher also wants a backup that costs **strictly more** than the cheapest route but as little as possible. Return the second smallest **distinct** total cost among all walks from depot 0 to depot `n - 1`. If fewer than two distinct costs exist (for example when depot `n - 1` cannot be reached, or when `n = 1` and there are no roads), return `-1`.

Input format

`n`: the number of depots. `roads`: an array of `[u, v, w]` two-way roads.

Output format

An integer: the second smallest distinct walk cost from depot 0 to depot n - 1, or -1.

Examples

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

Output: 7

The cheapest walk is 0-1-3 costing 5. The next distinct cost is 0-2-3 at 7. Longer walks that reuse roads cost more.

Input: n = 2, roads = [[0, 1, 4]]

Output: 12

The only road gives cost 4. Driving it back and forth adds 8 each time, so the next distinct cost is 4 + 8 = 12.

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

Output: -1

Depot 2 is not connected to depot 0, so there is no route at all and the answer is -1.

Constraints

1 <= n <= 10^4
0 <= roads.length <= 5 * 10^4
0 <= u, v < n, u != v
1 <= w <= 10^4
Parallel roads are allowed.

#graphs
#dijkstra
#shortest-path
#heap
#k-th-shortest