《机战佣兵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保证