#描述#
图的单源最短路径大家都耳熟能详了，再给大家做这样的题目应该会被你们BS吧。好吧，那今天我们就来点不一样的，不求最短，只求第二短。情形具体是这样的：一个无向图里有n个点和m条边，点的编号为1到n。现要你求出从节点1出发到节点n第二短的路径长度。何谓第二短：即路径总长度与最短路径的长度最接近但不相等。
注意：第二短的路线有可能会经过某些节点不止一次。

#格式#
##输入格式##
输入包含多组测试数据。
每组数据的第一行为两个整数n、m，分别表示点数和边数。
接下来有m行，每行包含三个整数a、b、c，表示节点a和节点b之间有一条边，边的长度为c。
1&lt=n&lt=5000，1&lt=m&lt=100000，1&lt=a、b&lt=n,1&lt=c&lt=5000。

##输出格式##
针对每组测试数据，输出第二短的路径长度。

#样例1#
##样例输入1##

3 3
1 2 1
2 3 1
1 3 1
2 2
1 2 2
1 2 2

##样例输出1##

2
6

#限制#
2000ms
65536KB

#提示#

#来源#