题目描述

贝茜搬到了一个小农场，有时会回去探望她的一位好朋友。她喜欢沿途的风景，不想太快到达，于是决定选择一条次短路径，而不是最短路径。她知道一定存在这样的次短路径。

乡间共有 $N$ 个路口，编号为 $1\sim N$，以及 $R$ 条双向道路。每条道路连接两个路口。贝茜从路口 $1$ 出发，她的朋友在路口 $N$。

次短路径可以与最短路径共用道路，也允许折返，即同一条道路或同一个路口可以经过多次。

这里的次短路径，是指在所有长度严格大于最短路径长度的路径中，长度最小的一条。如果有多条长度相同的最短路径，它们仍然都属于最短路径，不能把其中一条当成次短路径。

请计算从路口 $1$ 到路口 $N$ 的次短路径长度。

输入格式

第一行两个整数 $N,R$。

接下来 $R$ 行，每行三个整数 $A,B,D$，表示路口 $A$ 与路口 $B$ 之间有一条长度为 $D$ 的双向道路。

输出格式

输出一个整数，表示从路口 $1$ 到路口 $N$ 的次短路径长度。

4 4
1 2 100
2 4 200
2 3 250
3 4 100

450

4 4
1 2 100
2 4 200
2 3 250
3 4 100

450

4 4
1 2 100
2 4 200
2 3 250
3 4 100

450

说明/提示

样例中，路线 $1\to2\to4$ 的长度为 $100+200=300$；路线 $1\to2\to3\to4$ 的长度为 $100+250+100=450$。次短路径长度为 $450$。

数据范围

满足 $1\le N\le5000$，$1\le R\le100000$。

$1\le D\le5000$。