[USACO06NOV] Roadblocks G

题目描述

有 $N$ 个路口和 $R$ 条双向道路，每条道路连接两个路口并具有正整数长度。Bessie 从路口 $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

数据范围

对于所有数据，$1\le N\le 5000$，$1\le R\le 100000$，$1\le A,B\le N$，$1\le D\le 5000$。