Xiao Ming, a graduate of urban planning from the University of Waterloo, has come to work on urban planning for a region. This region has a total of $n$ cities and $n-1$ highways, ensuring that any two cities are connected by highways, though traveling between two cities requires paying a certain traffic fee. After studying this region in depth, Xiao Ming feels that the traffic fees in this region are too high. Xiao Ming wants to thoroughly renovate this region, but due to limited resources, he can only renovate one highway. The method of renovation is to remove one highway and rebuild a new highway of the same type (i.e., the same cost), such that the maximum traffic fee between any two cities in the region is minimized (i.e., the maximum traffic fee between any two cities is as small as possible), and it is guaranteed that any two cities are connected after the renovation. If you were Xiao Ming, how would you solve this problem?

Input

The first line of the input contains an integer $n$, representing the number of cities. The next $n-1$ lines each represent the initial $n-1$ highways. Each line contains three integers $u, v, d$, where $u$ and $v$ represent the city IDs at the two ends of the highway, and $d$ represents the traffic fee of this highway. $1 \le u, v \le n, 1 \le d \le 2000$

Output

The output contains only one integer, representing the maximum traffic fee between any two cities in the region after the optimal renovation.

Examples

Input 1

5
1 2 1
2 3 2
3 4 3
4 5 4

Output 1

7

Constraints

For 30% of the data, $1 \le n \le 500$ For 100% of the data, $1 \le n \le 5000$