시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

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 Pálvölgyi 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, . . . , 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 ≠ 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 10000. For 50% of the test cases, we will have 2 ≤ N ≤ 40 and 0 ≤ M ≤ 1000. All test cases will have 2 ≤ N ≤ 20000 and 0 ≤ M ≤ 100000.

예제 입력 1

4 6
1 2 5
1 3 5
2 3 1
2 4 5
3 4 5
1 4 13

예제 출력 1

11

There are two shortest routes of length 10 (1 → 2 → 4, 1 → 3 → 4) and the strictly-secondshortest route is 1 → 2 → 3 → 4 with length 11.

예제 입력 2

2 2
1 2 1
2 1 1

예제 출력 2

3

The shortest route is 1 → 2 of length 1, and the strictly-second route is 1 → 2 → 1 → 2 of length 3.