Highway Construction

As the head of the Accessible Commuting Movement (ACM), you have been lobbying the mayor to build a new highway in your city, and today your request was finally approved. There is one condition: you must submit a plan for the single best highway to build.

You have a map of every community in your city. Each community has a unique number, and any community may host a highway on-ramp. The map also shows a set of roadways connecting pairs of communities, each labelled with its driving distance. Between any two communities there is exactly one route through this network of roadways — that is, the communities and roadways form a tree.

You will build a single highway that runs back and forth between two communities of your choice. It replaces the unique chain of roadways between those two communities, and an on-ramp is built at every community along that chain. Residents of a community without an on-ramp must drive along the remaining roadways to the nearest community that has one in order to reach the highway.

Because long commutes are undesirable, you want to place the highway so that the longest drive from any community to its nearest on-ramp is as small as possible. Given the map with its roadways and driving distances, determine the farthest distance that any resident would have to drive to reach the nearest on-ramp once the highway is complete.

The input contains several test cases. Each test case describes one city map and begins with a line containing an integer $N$ ($2 \le N \le 100000$), the number of communities. The next $N - 1$ lines each contain three integers $i$, $j$ ($1 \le i, j \le N$) and $d$ ($1 \le d \le 10000$), meaning that communities $i$ and $j$ are joined by a roadway of driving distance $d$. The communities and roadways of each map form a tree. The input ends with a line containing $N = 0$, which must not be processed.

For each city map, output a single line containing one integer: the farthest distance from any community to its nearest on-ramp, when the highway is placed to make this distance as small as possible.