题目描述

小码君最近在玩一款古代城邦争霸游戏。他在游戏里占领了 $n$ 座城邦，编号为 $1$ 到 $n$。由于游戏中修建道路的成本比较高，但又要把这些城邦连起来，以便进行贸易和军事行动，所以他只建造了 $n-1$ 条双向道路，占领的 $n$ 座城邦之间由这 $n-1$ 条双向道路连通起来。

在该城邦争霸游戏中，每一条道路都会提供相应的游戏积分。每一条道路的积分计算规则是：该道路的长度 $\times$ 道路两端的城邦个数之差的绝对值。

小码君想知道现在这些道路总共可以给他提供多少积分。

例如，假设小码君有 $4$ 座城邦，在 $1$ 号和 $2$ 号有长度为 $1$ 的道路，在 $2$ 号和 $3$ 号之间有长度为 $2$ 的道路，在 $3$ 号和 $4$ 号之间有长度为 $3$ 的道路。

• 第一条道路长度为 $1$，它的一端只有 $1$ 号城邦，另一端有 $2,3,4$ 三座城邦，积分 = $1 \times |3 - 1| = 2$。
• 第二条道路长度为 $2$，一端有 $1,2$ 号城邦，另一端有 $3,4$ 号城邦，积分 = $2 \times |2 - 2| = 0$。
• 第三条道路长度为 $3$，一端有 $1,2,3$ 三座城邦，一端只有 $4$ 号城邦，积分 = $3 \times |3 - 1| = 6$。

总积分为 $2 + 0 + 6 = 8$。

请你帮助小码君计算出这 $n-1$ 条道路总共可以给他提供多少积分。

输入格式

第一行一个整数 $n$，表示城邦的个数。

接下来 $n-1$ 行，每行三个整数 $u_i, v_i, w_i$，表示在 $u_i$ 和 $v_i$ 两个城邦之间存在一条长度为 $w_i$ 的双向道路。

输出格式

共一行，一个整数，表示所有道路提供的总积分。

输入输出样例

输入 #1

4
1 2 1
2 3 2
3 4 3

输出 #1

8

输入 #2

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

输出 #2

20

输入 #3

5
1 4 5
2 3 7
5 1 9
2 5 4

输出 #3

49

说明/提示

数据范围

对于 $100\%$ 的数据，$2 \le n \le 10^6$，$1 \le u_i, v_i \le n$，$0 \le w_i \le 10^6$。