当前没有测试数据。

题目描述

给定一棵包含 $N$ 个节点的树，节点编号为 $1$ 到 $N$。树上的每条边都有一个权值。

定义两个节点 $u$ 和 $v$ 之间的距离 $d(u, v)$ 为它们之间路径上所有边的权值之和。

请计算所有无序节点对 $(u, v)$ ($1 \le u < v \le N$) 的距离之和，即：$\sum_{u=1}^{N} \sum_{v=u+1}^{N} d(u, v)$。

输入格式

第一行输入一个整数 $N$，表示树的节点数。

接下来 $N-1$ 行，每行包含三个整数 $u, v, w$，表示节点 $u$ 和节点 $v$ 之间有一条权值为 $w$ 的边。

输出格式

输出一个整数，表示所有无序节点对的距离之和。

样例 #1

输入

4
1 2 1
2 3 2
3 4 3

输出

19

样例 #2

输入

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

输出

30

样例说明

样例 1 解释

所有节点对的距离：

• $d(1,2) = 1$, $d(1,3) = 3$, $d(1,4) = 6$
• $d(2,3) = 2$, $d(2,4) = 5$
• $d(3,4) = 3$

总和：$1+3+6+2+5+3 = 20$... (实际计算可能需要重新验证)

数据范围

对于 $30\%$ 的数据，$2 \le N \le 100$。

对于 $100\%$ 的数据，$2 \le N \le 10^5$，$1 \le w \le 10^4$。