問題文
高桥不太喜欢公交车。然而,一旦踏入社会,就无法避免乘坐公交车的行为。
当您成为工作成年人时,您必须乘坐公共汽车从家到工作地点。高桥还没有收到工作机会,所以不知道公司在哪里。
高桥总是假设最坏的情况,即他在公交车上度过最长的时间。 我正在考虑搬到一个在最坏的情况下我可以在公共汽车上花费尽可能少的时间的地方。
附录:最坏的情况是,即使您选择要乘坐的巴士,公司所在地点的总巴士乘坐时间也将是最长的,因此总巴士乘坐时间将是最短的。而且,从家到上班的路上,高桥可以选择乘坐哪辆公交车,高桥会选择公交车总乘坐时间最短的路线。
每辆巴士都是2 公交车在两个公交车站之间往返,往返时间没有差别。 任何时候都可以乘坐公交车,而且可以忽略换乘的时间。
此外,您的家或办公室毗邻公交车站,因此您无法步行到另一个公交车站或乘坐公交车以外的任何方式出行。
找到高桥应该移动的地方,并输出他移动到那里时需要乘坐公共汽车的最长时间。
入力
输入是按以下格式从标准输入给出的。
N M a_1 b_1 t_1 a_2 b_2 t_2 : a_M b_M t_M
- 1 行包含一个表示公交车站数量的整数。 N (2 ≦ N ≦ 300) 和表示路线数量的整数 M (N - 1 ≦ M ≦ 44850) 用空格分隔。
- 继续 来自行 2 从行 M 行代表总线信息。 i 线包括公交车出发点和往返。 2 代表一巴士站的号码 a_i, b_i (1 ≦ a_i, b_i ≦ N) 和一个代表旅程需要多少分钟的数字 t_i (1 ≦ t_i ≦ 1000) 均以整数给出。
- 保证不存在无法到达的公交车站对。
- a_i ≠ b_i 有保证。
- 是 2 两个公交车站之间来回的路线最多有 1 仅存在一个。
出力
高桥搬家后,在公交车上呆的最长时间是 输出为 1 行。在输出末尾添加换行符。
入力例1
3 2 1 2 10 2 3 10
出力例1
10
巴士站 1 到巴士站 要转到 2 , 需要10 分钟。 巴士站 需要 1 到巴士站 要转到 3 , 需要20 分钟。 巴士站 需要 2 到巴士站 要转到 3 , 需要10 分钟。 因此,公交车站 当我移动到 2 时,最大骑行时间是 10 分钟,这是搬到的最佳地点。
入力例2
5 5 1 2 12 2 3 14 3 4 7 4 5 9 5 1 18
出力例2
26
巴士站 3 ,那将是最好的。
入力例3
4 6 1 2 1 2 3 1 3 4 1 4 1 1 1 3 1 4 2 1
出力例3
1
注意多条路线不走弯路。