The Runner-Up Route

Difficulty: 2000 4000 ms 128 MB

graphs shortest-paths

Print the STRICTLY second-shortest walk length from node 1 to node N (walks may repeat edges), or −1 if none exists.

Input: the first line has N and M; each of the next M lines has an undirected road u v w.

Output: the second-shortest distinct walk length, or −1.

Constraints:

• 2 ≤ N ≤ 10⁴
• 1 ≤ M ≤ 2×10⁴
• 1 ≤ w ≤ 10⁴

Sample Tests

4 4
1 2 1
2 4 1
1 3 1
3 4 2

3

2 1
1 2 3

9

Read the Editorial