問題文

yukicoder 市には $1$ から $N$ までの番号がついた $N$ 個の交差点があり、$N-1$ 本の双方向に通行できる道路でそれぞれ結ばれています。 ここで、任意の $2$ つの交差点間を、何本かの道路を通って行き来できることが保証されます（すなわち交差点を頂点、道路を辺とした木となります）。

このうち、$i$ 番目の道路は交差点 $A_i$ と $B_i$ を結んでおり、混雑度が $C_i$ となっています。また、市内の各道路の混雑度の最大値を「市全体の交通混雑度」と定め、 $D$ で表します。 あなたは $2$ つ交差点を選び、その $2$ 地点を結ぶ地下鉄を $1$ 本だけ建設することで、 $D$ の値をできるだけ小さくしたいと考えています。 地下鉄の建設によって各道路の混雑度が下記の影響を受ける時、 $D$ の達成可能な最小値はいくらでしょうか。

【混雑度の変化】
地下鉄が $2$ つの交差点 $p,q$ を結ぶとする。 このとき、$p,q$ 間の最短経路に含まれる道路について、そのような道路の混雑度の最小値を $m$ とすると、これらの道路の混雑度は全て同時に $m$ だけ減少する。 また、$p,q$ 間の最短経路に含まれない道路について、混雑度は変化しない。

入力

$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)$
• 与えられるグラフは木である
• $1\leq C_i\leq 10^9$ $(1\leq i\leq N-1)$
• 入力は全て整数である

出力

達成可能な「市全体の交通混雑度」$D$ の最小値を整数で出力してください。 最後に改行してください。

サンプル

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