Tree - Diameter of a Tree

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

木の直径

非負の重みをもつ無向の木 T の直径を求めてください。木の最遠頂点間の距離を木の直径といいます。

入力

n
s1 t1 w1
s2 t2 w2
:
sn − 1 tn − 1 wn − 1

1行目に木の節点数を表す整数 n が与えられます。木の節点には、それぞれ 0 から n-1 の番号が付けられているものとします。

続く n-1 行に、木の辺が与えられます。sitii 番目の辺の端点を表し、wii 番目の辺の重み(距離)を表します。

出力

直径を1行に出力してください。

制約

  • 1 ≤ n ≤ 100,000
  • 0 ≤ wi ≤ 1,000

入力例 1

4
0 1 2
1 2 1
1 3 3

出力例 1

5

入力例 2

4
0 1 1
1 2 2
2 3 4

出力例 1

7

Note

      解説