Description

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

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

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

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

## Input Format

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

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

## Output Format

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

```input1 5 3 1 4 5 4 5 1 1 2 7 ``` ```output1 6 ``` ```input2 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 ``` ```output2 28 ``` ## Hint

对于$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$；