Minimizing the Maximum Traffic Cost

A city planning expert is assigned to reduce the maximum travel cost between any two cities in a region. The region has n cities and n-1 highways forming a tree (i.e. any two cities are connected by unique highways). Each highway has a toll cost. Due to limited resources, you are allowed to perform exactly one transformation on the highway network. The transformation consists of:

• Remove one highway, which splits the network into two connected components.
• Add a new highway with the same cost as the one removed that connects any city from the first component and any city from the second component so that the network remains connected.

The goal is to choose which highway to modify (remove and re-add) so that the maximum travel cost (i.e. the diameter of the resulting tree) between any two cities is minimized. When connecting the two components, you can optimally choose the two "centers" (the nodes that minimize the radius) of the two trees. For a tree, the radius is \( \frac{diameter+1}{2} \) (using integer ceiling division).

Task: Given the network and the cost of each highway, determine the minimum possible maximum travel cost after performing the single optimal highway modification.

The answer is computed as follows. For each highway removed with cost \(w\), let the two resulting trees have diameters \(d_1\) and \(d_2\). Their corresponding radii are \(r_1 = \lceil d_1/2 \rceil\) and \(r_2 = \lceil d_2/2 \rceil\). If we add a highway (with cost \(w\)) connecting the two centers, the new diameter becomes:

[ D = \max\Big(d_1,; d_2,; r_1 + r_2 + w\Big). ]

Your task is to output the minimum \(D\) over all choices of edges to remove.

inputFormat

The first line contains an integer n (2 ≤ n ≤ 10⁵), representing the number of cities. Each of the next n-1 lines contains three integers u, v, and w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 10⁹), meaning that there is a highway between city u and city v with a toll cost of w.

outputFormat

Output a single integer – the minimum possible maximum travel cost (diameter) after performing the highway modification optimally.

sample

4
1 2 3
2 3 2
3 4 4

6