You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

《机战佣兵VI 境界天火》将以FromSoftware多年的机甲游戏技术为基础，结合坚实的游戏性提供给玩家FromSoftware近年动作游戏般的突破性游戏体验。 youngmagician最近迷上了装甲核心6，现在已知youngmagician操控的机甲处于1号点，而敌人位于n号点，在不同的点位间存在需要消耗一定能量值的路径，如果机甲的能量值不够，将无法通过这条路径，但是当机甲处于不同点位时可以等待能量回复至能量上限，现在youngmagician想要进攻位于点n的敌人，但是他想尽可能的少分配能量相关配件给自己的机甲以增强火力，你能告诉youngmagician最低的能量上限是多少吗？

Input Format

第一行输入两个整数 n,m;表示有n个点位和m条路径。 接下来m行，每一行输入3个数字u,v,w。表示从u到v存在一条需要能量w的路径，注意，相同的两点间可能有多条路径。 数据保证一定存在一条从1到n的路径，不存在自环。

Output Format

一个整数，表示需要的最低能量上限。

Sample

样例输入

4 4
1 4 114
1 2 5
2 3 1
3 4 4

样例输出

5

样例解释 从1到4存在两条路径：（1）1->4,经过的所需路径的能量上限为514.（2）1->2->3->4,经过所需的能量上限为1->2的5.故答案输出5.

Hint

对于所有数据，保证$1\leq n \leq 40000$，$1\leq m \leq 200000$ ,对于每一条边u,v,w保证$1\leq w \leq 1e9$