問題文


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

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

制約


  • 入力は全て整数

入力





出力


最大となる 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

Submit


Go (1.14)