遺伝子の木とは、さまざまな遺伝子や生物種の進化を示す木である。遺伝子の木は、祖先に関する仮定を置かずに、葉の頂点に格納された特定の遺伝子間の関係を表す。葉の頂点は分類群（taxa）と呼ばれる遺伝子を表し、内部頂点は推定される祖先の分類群を表す。木の各辺には系統発生的長さという正の整数が対応し、その辺の 2 頂点間の進化的距離を定量化する。例えば、下の左の図は 6 つの分類群の関係を近似する、葉が 6 つある遺伝子の木で、右の図は 4 つの分類群の遺伝子の木である。

図 B.1：根なしの遺伝子の木 $T_1,T_2$。

上の木 $T_1,T_2$ のように、遺伝子の木は、すべての内部頂点（葉でない頂点）の次数が 3 の根なし木としてモデル化される。2 つの葉の頂点間の経路長とは、それらを結ぶ唯一の経路上の辺の系統発生的長さの和である。$T_1$ では、Human と Cow の経路長は $2+3=5$、Human と Goldfish の経路長は $2+4+8+10=24$ である。これらの長さは、遺伝的に Human は Goldfish より Cow にはるかに近いことを示す。$T_2$ から、Human に最も近い霊長類は Chimpanzee だと推測できる。

研究者は木の中の遺伝子間の距離の測定に関心がある。有名な距離尺度は、順序を区別しないすべての葉の組についての経路長の二乗和である。より正確には、その距離 $d(T)$ は次のように定義される。

$$d(T)=\sum_{\text{順序を区別しない組 }(u,v)}p_{u,v}^2.$$

ここで $p_{u,v}$ は $T$ 内の 2 つの葉の頂点 $u,v$ の経路長である。$d(T)$ は $T$ の順序を区別しないすべての葉の組 $u,v$ にわたる経路長の二乗 $p_{u,v}^2$ の和であることに注意せよ。図 B.1 の遺伝子の木 $T_2$ には、順序を区別しないすべての葉の組に対して 6 本の経路がある：(Human, Chimpanzee), (Human, Gorilla), (Human, Orangutan), (Chimpanzee, Gorilla), (Chimpanzee, Orangutan), (Gorilla, Orangutan)。経路長の二乗和は $2^2+4^2+5^2+4^2+5^2+5^2=111$ なので、$d(T_2)=111$ である。

根なしの遺伝子の木 $T$ が与えられる。$d(T)$ を出力するプログラムを書け。

入力

プログラムは標準入力から読み込む。入力は、入力される遺伝子の木 $T$ の頂点数である整数 $n$ ($4\le n\le100\,000$) を含む行で始まる。$T$ は $n-1$ 本の辺を持つ。$T$ の頂点は $1$ から $n$ までの番号が付いている。続く $n-1$ 行は $T$ の $n-1$ 本の辺を表し、各行には 3 つの非負整数 $a,b,l$ ($1\le a\ne b\le n$, $1\le l\le50$) が含まれる。2 頂点 $a,b$ は系統発生的長さ $l$ の辺をなす。

出力

プログラムは標準出力に書き込む。ちょうど 1 行出力せよ。その行には正の整数 $d(T)$ が 1 つ含まれなければならない。

以下に 3 つのテストケースの入力例と出力例を示す。

入出力例

入力 1

4
1 4 1
4 3 1
2 4 1

出力 1

12

入力 2

6
1 5 1
5 2 1
5 6 1
6 4 3
6 3 2

出力 2

111

入力 3

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

出力 3

4709