Alex is planning rest area placements on a simplified model of Taiwan’s freeway system. The system contains interchanges, connected by bidirectional roads. The network is connected, and there is exactly one shortest route between any pair of interchanges. The -th road connects interchanges and , and has a length of .
Exactly rest areas with gas stations can be built, each located at an interchange. A driver may start a trip from any interchange and travel to any other, always following the unique shortest path. They begin each trip with a full tank of gas and can refuel only at interchanges that have a rest area.
Alex is curious about the smallest possible fuel tank capacity such that it’s possible to place the rest areas in a way that ensures no driver will ever run out of gas. On any trip, the driver must never have to travel more than units along the path without passing through a rest area, including at the beginning or end of the journey. The goal is to figure out the minimum such , assuming the rest areas are placed in the best possible way.
输入格式
The first line contains two integers .
Followed by lines, the -th of which contains three integers , representing the -th road connects interchanges and with a length .
输出格式
Output one integer, the smallest possible fuel tank capacity .
样例
样例输入 1
5 1
1 2 3
1 5 2
2 3 3
2 4 1
样例输出 1
5
样例输入 2
5 2
1 2 3
1 5 2
2 3 3
2 4 1
样例输出 2
3
数据范围与提示
It is guaranteed that the input roads form a tree.
