All problems

Toll Road Coupon

Hard · shortest path

A region has n towns, numbered 0 to n - 1, joined by two-way toll roads. Each road is given as [a, b, toll]: you can drive between towns a and b in either direction and pay toll every time you use it.

You are travelling from town 0 to town n - 1 and you hold one coupon. The coupon makes a single drive along one road of your choice free (the toll for that one drive is 0). You do not have to use it. A road can be driven more than once, but the coupon only covers one drive.

Return the smallest total toll you can pay to get from town 0 to town n - 1, or -1 if there is no way to get there.

There may be several roads between the same two towns, and a road may start and end in the same town.

Examples

Example 1

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

Output: 5

The only route is 0, 1, 2. Using the coupon on the toll of 7 leaves 5 to pay.

Example 2

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

Output: 3

Go 0, 2, 3 for 3 + 9 = 12, and use the coupon on the road with toll 9, which leaves 3. The other route costs 4 even with its best coupon.

Example 3

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

Output: -1

No road leads to town 2, so it cannot be reached.

Constraints