《机战佣兵VI 境界天火》将以FromSoftware多年的机甲游戏技术为基础，结合坚实的游戏性提供给玩家FromSoftware近年动作游戏般的突破性游戏体验。 youngmagician最近迷上了装甲核心6，现在已知youngmagician操控的机甲处于1号点，而敌人位于n号点，在不同的点位间存在需要消耗一定能量值的路径，如果机甲的能量值不够，将无法通过这条路径，但是当机甲处于不同点位时可以等待能量回复至能量上限，现在youngmagician想要进攻位于点n的敌人，但是他想尽可能的少分配能量相关配件给自己的机甲以增强火力，你能告诉youngmagician最低的能量上限是多少吗？
第一行输入两个整数 n,m;表示有n个点位和m条路径。 接下来m行，每一行输入3个数字u,v,w。表示从u到v存在一条需要能量w的路径，注意，相同的两点间可能有多条路径。 数据保证一定存在一条从1到n的路径，不存在自环。
一个整数，表示需要的最低能量上限。
样例输入
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.
对于所有数据，保证， ,对于每一条边u,v,w保证
