Problem H : Dungeon (II)

あなたはとあるゲームの開発に携わっている。 そのゲームはランダムに生成されたダンジョンをプレイヤーが探索するというものである。 ゲームの仕様として、プレイヤーに予めダンジョンの危険度を提示し、生成されたダンジョンを探索するのか、それとも新しくダンジョンを生成しなおすかを、選択できるようにしたい。

このゲームで生成されるダンジョンにはn 個の部屋が存在しており、0から n-1 までの番号が割り振られている。 部屋と部屋は通路で結ばれている。部屋と部屋を結ぶ通路は、合計で n-1 本存在している。 通路はどちらの方向へも進むことができる。 また、部屋と部屋の間には距離が設定されている。 生成されたダンジョンではいくつかの通路を経由して、ある部屋から他のすべての部屋へ行くことが可能である。 そして、プレイヤーがゲームを行う際に、２つの異なる部屋がスタート地点とゴール地点として選ばれる。

あなたはダンジョンの評価を行うために、危険度の評価方法を決めることにした。 まず、ある部屋から別の部屋までに移動する際の危険度を、部屋間を最短で移動するために使う通路の中で、最もコスト高い通路の値とする。 そして、ダンジョンの危険度を、i < j となる部屋のペアの間を移動する際の危険度の総和とすることにした。

ランダムに生成されたダンジョンのが入力として与えられる。 まず、i < j となるすべての部屋のペアについて、移動する際の危険度を計算して欲しい。 そして、その総和を問題の答えとして出力せよ。

Input

入力は以下のフォーマットで与えられる。

n
a1 b1 c1 
.
.
.
an-1 bn-1 cn-1 

a_i b_i c_i は 部屋 a_i と b_i　を結ぶ通路の距離がc_iであることを表す。

入力は以下の制約を満たす
2 ≤ n ≤ 200,000
0 ≤ a_i,b_i < n
0 ≤ c_i ≤ 100,000

Output

答えの値を1行に出力せよ

Sample Input 1

4
0 1 3
1 2 5
1 3 2

Sample Output 1

23

Sample Input 2

6
0 2 5
2 1 1
2 3 10
3 5 4
3 4 2

Sample Output 2

111