AT_agc018_d [AGC018D] Tree and Hamilton Path

[problemUrl]: https://atcoder.jp/contests/agc018/tasks/agc018_d $ N $ 頂点の木があり、頂点には $ 1 $ から $ N $ の番号がついています。 この木の $ i $ 番目の辺は頂点 $ A_i $ と $ B_i $ を結んでいて、その長さは $ C_i $ です。 joisinoお姉ちゃんは、$ N $ 頂点の完全グラフを作りました。 なお、この完全グラフの頂点 $ u $ と $ v $ を結ぶ辺の長さは、木での頂点 $ u $ と $ v $ の最短距離になっています。 joisinoお姉ちゃんは、この完全グラフのハミルトンパス(※)のうち、最も長いものの長さを知りたくなりました。 joisinoお姉ちゃんの作った完全グラフのハミルトンパスのうち、最も長いものの長さを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ : $ $ A_{N-1} $ $ B_{N-1} $ $ C_{N-1} $

joisinoお姉ちゃんの作った完全グラフのハミルトンパスのうち、最も長いものの長さを出力せよ。

### 注釈 あるグラフのハミルトンパスとは、そのグラフのパスであって、すべての頂点をちょうど一度だけ通るようなものを指します。 ### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ A_i\