问题描述

高桥君不太喜欢坐公共汽车。但是，一旦进入社会，就无法避免乘坐公交车。

成为上班族后，高桥君必须坐公交车从家里去公司。由于高桥君还没有确定的工作机会，所以不知道公司的位置在哪里。

高桥君总是假设最糟糕的情况，也就是乘坐时间最长的情况。他计划搬到一个位置，使得乘坐这个最糟糕情况下的公交车时间尽可能地缩短。

补充说明：最糟糕的情况是指在选择乘坐公交车时，选择乘坐时间总和最短的公交车后，导致乘坐时间总和最长的情况。并且在从家到公司的路上，高桥君可以选择乘坐的公交车，并且高桥君将选择总乘坐时间最短的路径。

每辆公交车都往返于两个公交车站之间，来回所需时间相同。可以随时乘坐公交车，忽略换乘所耗费的时间。

此外，家和公司紧邻公交车站，无法步行到其他公交车站或使用其他交通工具进行移动。

请找出高桥君应该搬到的位置，并输出搬迁后必须乘坐公交车的最长时间。

输入

输入以以下格式从标准输入中给出。

$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)$。
• 接下来的 M 行表示公交车的信息。每行表示第 i 辆公交车往返的两个公交车站编号 $a_i$, $b_i (1 ≦ a_i, b_i ≦ N)$，以及所需时间 $t_i (1 ≦ t_i ≦ 1000)$。
• 保证不存在无法到达的公交车站配对。
• 保证 $a_i ≠ b_i$。
• 每对公交车站之间的线路最多只有一条。

输出

假设高桥君搬家后，在最糟糕的情况下必须乘坐公交车的时间最长，用一行输出这个时间。输出末尾加上换行符。

示例 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

请注意，即使有多条路径，也应避免绕远路。