OI题库

【题目背景】

小明在做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|的值。

【输入文件】

输入文件第一行是两个整数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分钟。

【输出文件】

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

【样例输入】

4 3
1 2 1
2 3 1
3 4 1

【样例输出】

4