题目描述 Description

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 Sz´echenyi thermal bath (s for short) and ending at the Tomb of G¨ ul Baba (t for short).


Naturally, you want to complete the race as quickly as possible, because you will get more promo- tional 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´alv¨olgyi 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.


输入描述 Input Description

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.

第一行包含两个整数N和M,N代表布达佩斯的节点个数,M代表边的个数。节点编号从1到N。1代表出发点s,N代表终点t。接下来的M行每行三个整数A B L,代表有一条从A到B的长度为L的单向同路。你可以认为A不等于B,也不会有重复的(A,B)对。

输出描述 Output Description

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.


样例输入 Sample Input


4 6

1 2 5

1 3 5

2 3 1

2 4 5

3 4 5

1 4 13


2 2

1 2 1

2 1 1

样例输出 Sample Output





数据范围及提示 Data Size & Hint


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


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

<:SECTION id=statistics>