题目描述：

牛宝宝不太喜欢公共汽车。但是一旦进入社会，就不能避免乘坐公共汽车的行为。

成为社会人的话，从家到公司必须坐巴士去。牛宝宝还没有拿到offer，所以不知道公司的位置。

牛宝宝经常设想乘坐巴士的时间最长的最坏情况。想搬到一个即使最坏情况下，坐巴士的时间也尽可能短的地方。

这里最坏情况是指公司刚好位于距离家最远的地方

各巴士往返于两个公交车站，来回所需的时间没有差别。任意时刻都可以乘坐巴士，可以无视换乘所需的时间。

另外家和公司与公交车站相邻，不能走路其他公交车站，也不能用巴士以外的方式移动。

求高桥君应该搬家的地方，输出搬到那里时乘坐巴士到公司的时间最大值。

输入格式：

第一行两个整数$n$和$m$ 其中$n$表示公交站的数目，$m$表示公交线路个数 接下来m行，每行三个整数$a,b,c$ 分别表示$a,b$两站间存在公交，乘坐需要花费$c$时间

输出格式：

样例：

5 5
1 2 12
2 3 14
3 4 7
4 5 9
5 1 18

26

提示

样例说明：搬家到3号公交站附近，最坏的情况下公司在1号公交站，需要26单位时间

$1<=n<=300$

$n<=m<=1000$

$1<=a,b<=n$

$1<=c<=1000$

保证图连通