Problem Statement

yukicoder City has $N$ intersections numbered from $1$ to $N$, connected by $N-1$ bidirectional roads. Here, it is guaranteed that any $2$ intersections can be reached from each other by passing through some number of roads (that is, the intersections as vertices and the roads as edges form a tree).

Among these, the $i$-th road connects intersections $A_i$ and $B_i$ and has a congestion level of $C_i$. The maximum of the congestion levels of the roads in the city is defined as the "overall traffic congestion level of the city" and is denoted by $D$. You want to choose $2$ intersections and build exactly $1$ subway line connecting those $2$ points, so as to make the value of $D$ as small as possible. Given that building the subway affects the congestion level of each road as described below, what is the minimum achievable value of $D$?

[Change in Congestion Levels]
Suppose the subway connects $2$ intersections $p,q$. Then, for the roads on the shortest path between $p,q$, let $m$ be the minimum congestion level among those roads; the congestion levels of these roads all decrease by $m$ simultaneously. The congestion levels of roads not on the shortest path between $p,q$ do not change.

Input

$N$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
...
$A_{N-1}$ $B_{N-1}$ $C_{N-1}$

• $2\leq N\leq 2\times 10^5$
• $1\leq A_i,B_i\leq N$ $(1\leq i\leq N-1)$
• The given graph is a tree
• $1\leq C_i\leq 10^9$ $(1\leq i\leq N-1)$
• All inputs are integers

Output

Output the minimum achievable value of the "overall traffic congestion level of the city" $D$ as an integer. Print a newline at the end.

Sample

4
1 2 1
2 3 2
3 4 3

1

4
2 1 100
3 1 90
4 1 80

80

9
1 2 15
3 1 10
2 4 8
5 6 7
5 2 9
3 8 7
7 3 2
3 9 5

8