Park walk

問題文

さめくんは公園で歩くルートを考えています。
公園には $N$ 個のチェックポイントがあり、それぞれ $1$ から $N$ の番号が付けられています。
さらに $N-1$ つの道があり、$i$ 番目の道は $A_i$ と $B_i$ を距離 $C_i$ で繋いでいます。
道をいくつか辿ることで、どのチェックポイントも互いに行き来することができます。
また、道以外を歩いて移動することはできません。

さめくんは 2 つのチェックポイントを選び、その間を最短距離で歩くことにしました。
この時、歩く距離の最大値を求めてください。

制約

• $2 \le N \le 10^4$
• $1 \le A_i < B_i \le N$
• $1 \le C_i \le 100$
• 入力は全て整数

入力

出力

最大となる 2 つのチェックポイント間の距離を出力してください。

入力例1

4
1 2 3
2 3 4
2 4 5

出力例1

9

チェックポイント 3 と 4 を選ぶことで距離 9 を歩くことになります。

入力例2

3
1 2 8
1 3 3

出力例2

11

入力例3

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

出力例3

28