Canadian Computing Competition: 2012 Stage 2, Day 1, Problem 2
Welcome to the Hungary Games! The streets of Budapest form a twisted network of one-way streets. You have been forced to join a race as part of a "Reality TV" show where you race through these streets, starting at the Szechenyi thermal bath (~s~ for short) and ending at the Tomb of Gul Baba (~t~ for short).
Naturally, you want to complete the race as quickly as possible, because you will get more promotional contracts the better you perform. However, there is a catch: any person who is smart enough to take a shortest ~s~-~t~ route will be thrown into the Palvolgyi cave system and kept as a national treasure. You would like to avoid this fate, but still be as fast as possible. Write a program that computes a strictly-second-shortest ~s~-~t~ route.
Sometimes the strictly-second-shortest route visits some nodes more than once; see Sample Input 2 for an example.
The first line will have the format ~N~ ~M~, where ~N~ is the number of nodes in Budapest and ~M~ is the number of edges. The nodes are ~1, 2, \dots, N~; node ~1~ represents ~s~; node ~N~ represents ~t~. Then there are ~M~ lines of the form ~A~ ~B~ ~L~, indicating a one-way street from ~A~ to ~B~ of length ~L~. You can assume that ~A \ne B~ on these lines, and that the ordered pairs ~(A, B)~ are distinct.
Output the length of a strictly-second-shortest route from ~s~ to ~t~. If there are less than two possible lengths for routes from ~s~ to ~t~, output ~-1~.
Every length ~L~ will be a positive integer between ~1~ and ~10\,000~. For 50% of the test cases, we will have ~2 \le N \le 40~ and ~0 \le M \le 1000~. All test cases will have ~2 \le N \le 20\,000~ and ~0 \le M \le 100\,000~.
Sample Input 1
4 6 1 2 5 1 3 5 2 3 1 2 4 5 3 4 5 1 4 13
Output for Sample Input 1
There are two shortest routes of length 10 ~(1 \to 2 \to 4, 1 \to 3 \to 4)~ and the strictly-second-shortest route is ~1 \to 2 \to 3 \to 4~ with length 11.
Sample Input 2
2 2 1 2 1 2 1 1
Output for Sample Input 2
The shortest route is ~1 \to 2~ of length 1, and the strictly-second route is ~1 \to 2 \to 1 \to 2~ of length 3.