测试数据来自 system/2225

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H准备从他所在的城市前往另一个城市旅行!在这个国家中每两个城市之间最多只有一条高速公路相通，并且我们知道从一个城市到另一个城市路上所需花费的时间。

　　小H在出发前，无意中听到有一条高速路正在维修，并且那儿正堵车，但没听清楚到底是哪一条路。但由于这个国家的交通非常发达，所以无论哪一条路正在维修，小H从他所在的城市都能到达目的地城市。小H将只从不堵车的路上通过，并且她将按最短路线行车。他想知道在最糟糕的情况下到达目的地城市最少需要多长时间？请你编写程序找到按最短路线通过不堵车道路到达目标城市所需的最长时间(用分钟表示)。

【输入格式】

　　第一行有两个用空格隔开的数 \(N\) 和 \(M\)，分别表示城市的数量以及城市间道路的数量。城市用数字 1 至 \(N\) 标识，小H在城市 1 中，旅行目的地城市为 \(N\) 。
　　接下来的 \(M\) 行中每行包含三个用空格隔开的数 \(A，B\) 和 \(V\) 。其中 \(1≤A,B≤N，1≤V≤1000\)。这些数字表示在城市 \(A\) 和城市 \(B\) 中间有一条双行道，并且在 V 分钟内就能通过。

【输出格式】

　　输出一个整数，表示在这个整数时间中，无论哪条路在堵车，小H应该能够到达 \(N\) 号城市；如果少于这个时间的话，则必定存在一条路，该条路一旦堵车，小H就不能够到达城市N。

【输入输出样例】

　Input

6 8
1 3 10
1 5 12
3 4 6
5 6 3
4 5 12
3 6 4
4 2 5
6 2 24

　Output

15

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤1000\)，\(1≤M≤N*(N-1)/2\)。

【来源】

　　Mr.he