题目描述

在 $EVE$ 游戏中，宇宙被划分成为许多区域，每个区域中都有数目不定的星门，可以通过星门来跳跃到特定的区域（星门是双向的）。

现在你正参与 $BBE$ 联军与 $MLGBD$ 联盟的会战，但由于飞船受损，需要尽快回到后方的友军空间站进行维护。

试编写程序，计算出所须的最短的返回空间站时间。

为了简化问题，我们约定飞船所在的位置为区域 $1$，空间站所在的位置为区域 $N$。

输入格式

第$1$行，两个整数$N$,$M$，分别为区域的总数和星门的总数；

第$2..M+1$行，每行三个整数$X[i],Y[i],Z[i]$，分别为星门连接的两个区域，以及跳跃所需时间；

输出格式

一个整数，返回空间站所需的最短时间。

样例

输入

5 3
1 4 5
4 5 1
1 2 7

6

输出

10 11
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9
8 9 10
9 10 11
1 5 7
6 9 3

28

提示

对于$80\%$的数据，$1<N<=10000,1<M<50000$；

对于$100\%$的数据，$1<N \le 30000，1<M<150000，1 \le X[],Y[] \le N，1 \le Z[] \le 4096$；