当前没有测试数据。

Description

小明在做NOI2003练习赛的《幸福的老鼠》时觉得题目太简单了，于是对原题做了一些扩展：

• 将原题的N从20扩展到200000。

• 将原题经过一条街道需要的时间改为Ti（1 £ Ti £ 1000000000）分钟（i为街道的编号）。

• 增加了一个条件：小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离。

即使这样，他仍然很快地做了出来。于是，小明打算做一些输入文件来测试他的程序。现在他已经生成了一些符合题意的图，不过为了增大测试数据的难度，他希望你能帮他选取一组X、Y、Z，使老鼠拿到礼物的时间尽可能地大。

【小明扩展的题目（注意，你并不需要解决此题）】

幸福的老鼠Jerry要过生日了，小狗大狗分别送了它一份生日礼物。现在Jerry打算从自己家X出发，先到小狗家Y （因为小狗家Y离老鼠家X的距离小于等于大狗家Z离老鼠家X的距离） ，再到大狗家Z，将两份礼物取回。

卡通城由N（3 £ N £ 200000）个居住点和N-1条连接居住点的双向街道组成， 经过第i条街道需花费Ti（1 £ Ti £ 1000000000）分钟的时间 。可以保证，任两个居住点间都存在通路。

不妨设Jerry家在点X，小狗家在点Y，大狗家在点Z。现在，请你计算，Jerry最快需要耗费多长时间才能拿到生日礼物？

【任务描述】

定义：令|AB|表示卡通城中从A点走到B点需要的最少时间。 给出卡通城的地图，找到一组X、Y、Z，使得： |XY|≤|XZ| |XY|+|YZ|最大。 并求出此时|XY|+|YZ|的值。

Format

Input

输入文件jerrygen.in第一行是两个整数N（3 £ N £ 200000）和M（M=N-1），分别表示居住点总数和街道总数。从第2行开始到第N行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti（1£Ui, Vi £ N，1 £ Ti £ 1000000000），表示街道i连接居住点Ui和Vi，并且经过街道i需花费Ti分钟。

Output

输出文件jerrygen.out仅包含一个整数T，即|XY|+|YZ|的最大值。

Samples

4 3
1 2 1
2 3 1
3 4 1

4