P3761 [TJOI2017] City

After graduating from the Urban Planning program at Gariton University, Xiao Ming joined a regional Urban Planning Bureau. This region has $n$ cities and $n-1$ highways, ensuring that any two cities are mutually reachable via highways. However, traveling through a highway requires paying a transportation cost. After careful study, Xiao Ming thinks the transportation cost in this region is too high. Xiao Ming wants to completely overhaul the region, but due to limited resources from his supervisor, he can only modify exactly one highway. The modification is to remove one highway and rebuild one identical highway (i.e., with the same transportation cost), so that the maximum transportation cost between any two cities is minimized (that is, the transportation cost between the pair of cities with the largest cost is as small as possible), and it must still be guaranteed that any two cities remain mutually reachable after reconstruction. If you were Xiao Ming, how would you solve this problem?

The first line contains an integer $n$, the number of cities. The next $n-1$ lines describe the initial $n-1$ highways. Each line contains three integers $u, v, d$. Here $u, v$ are the labels of the two endpoint cities of this highway, and $d$ is its transportation cost. $1 \leq u, v \leq n$, $1 \leq d \leq 2000$.

Output a single integer: after the optimal reconstruction, the maximum transportation cost between any two cities.

For 30% of the testdata, $1 \leq n \leq 500$. For 100% of the testdata, $1 \leq n \leq 5000$. Translated by ChatGPT 5