2935: 桐人的约会

这是一个风和日丽的日子，桐人和诗乃在约会。他们所在的城市共有N 个街 区，和M 条道路，每条道路连接两个不同的街区，并且通过一条道路需要花费一 些时间。他们现在处于N 号街区，正在享受幸福时光的桐人完全忘记了他的手机 被亚丝娜安装了监控装置的事情，此时亚丝娜已经得知了桐人的位置以及他正在 和一个妹子约会的事实，十分愤怒，于是从她所在的1 号街区火速赶往N 号街区。 现在这个城市中有一条道路正在维修，不能通行，不过不论是哪条道路处于维修 中，均存在一条路径可以从1 号街区前往N 号街区，而且亚丝娜一定会选取最短 路前往N 号街区。现在你很好奇，桐人的美好时光最多还能持续多久，即亚丝娜 最多要花费多长的时间才能到达N 号街区。

输入第1 行两个正整数N 和M，N 表示街区个数，M 表示道路数。 第2 到M+1 行，每行三个整数u,v,w 表示存在一条连接u 和v 的道路，通 过这条道路花费的时间为w，数据保证没有重边和自环。

输出一行一个整数，表示最多花费的时间。

5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10

27