题目描述

高桥君，不太喜欢公共汽车。

但是，一进入社会，就无法避免乘坐公共汽车的行为。

进入社会后，从自家到公司，必须坐公共汽车上班。高桥君还没拿到录取单，不知道要进入哪家公司，自然也就不知道公司在哪儿。高桥君经常想象乘坐巴士情况。他只想象时间最长、最坏的情况。我想把乘坐这个最坏情况的巴士的时间搬到让高桥君上班时间尽量缩短的地方。

PS：最坏的情况是指，乘坐巴士的时间合计最短，选择所乘坐的巴士时，是指在坐公共汽车的时间合计会变长的位置有公司的情况。

另外，从家中去公司时，可以选择高桥乘坐的巴士，高桥君选择乘坐巴士的时间合计最短的路径。各巴士在 $2$ 个公交车站来回行驶，去、回所需时间没有差别。随时都可以乘坐巴士，可以忽略转乘所花费的时间等。

另外，自家和公司与公共汽车站相邻，不能步行到其他巴士站，也不能通过巴士以外的方法进行移动。为高桥君找个搬家的地方，请输出搬到那里时，要坐公交车时间的最大值。

输入格式

在第一行，以空格分隔提供表示停靠站数的整数 $N(2\le N\le 300)$ 和表示路线数量的整数 $M(N-1\le M\le 44850)$。

接下来的第 $2$ 行到 $M$ 行表示总线的信息。在第 $i$ 行中，表示与总线的出发地点往返的 $2$ 个停靠站的编号 $a_i,b_i(1\le a_i,b_i\le N,b_{i+1}\le a_i,b_i\le N)$，和表示该移动需要多少分钟的数字 $t_i(1\le t_i\le 1000)$，分别由整数给出。保障了不存在的巴士站的对不存在。保证 $a_i\ne b_i$。

在某 $2$ 个停靠站上往返的路线只有 $1$ 个。

输出格式

如题，注意末尾要换行。

感谢 @longtaoxuan 提供的翻译。