Description

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

Input

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

Output

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

Sample

Input

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

Output

2
6