#1031. youngmagician是装甲核心高手

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: admin

题目描述

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

输入格式

第一行输入两个整数 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保证