题目背景

在一片遥远的国度里，小珅是这片疆域的国王，小泽是他最得力的工程大臣。

整个国家由$n$座城市组成，城市之间依靠古老的道路连接，整体构成一棵树的结构。为了发展国家，小珅决定对所有道路进行翻新修建，每条道路都有对应的修建花费。

小泽需要规划修建方案，同时计算出修建总花费的参考值：每条道路的修建花费 × 这条道路分割国家后形成的两侧城市数量之差，最后把所有道路的贡献相加。

请你帮助小泽完成计算，让国家的道路翻新工程顺利启动。

题目描述

给定一棵包含$n$个节点的树，每条边有一个正整数权值。

请你求出所有边的贡献值之和。

本题中，删除一条边后，树会分成大小分别为 $s$ 和 $n-s$ 的两部分；若该边权值为 $w$，则这条边的贡献值定义为 $w\times|s-(n-s)|$。

输入格式

第一行一个整数$n$，表示城市数量。

接下来$n-1$行，每行三个整数$u,v,w$，表示城市$u$和城市$v$之间有一条权值为$w$的道路。

输出格式

输出一行一个整数，表示所有边的贡献值之和。

输入输出样例

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

20

说明/提示

对于 $100\%$ 的数据，$1\leq a_i, b_i\leq n$，$0\leq c_i\leq10^6$，$2\leq n\leq 10^6$。 |测试点编号|$n=$| |:-:|:-:| |$1$|$2$| |$2$|$10$| |$3$|$100$| |$4$|$200$| |$5$|$500$| |$6$|$600$| |$7$|$800$| |$8$|$1000$| |$9$|$10^4$| |$10$|$2\times 10^4$| |$11$|$5\times 10^4$| |$12$|$6\times 10^4$| |$13$|$8\times 10^4$| |$14$|$10^5$| |$15$|$6\times 10^5$| |$16$|$7\times 10^5$| |$17$|$8\times 10^5$| |$18$|$9\times 10^5$| |$19,20$|$10^6$|

2
1 2 248

0

19
1 2 849
1 3 429
3 4 21
4 5 397
4 6 885
2 7 683
3 8 1000
1 9 548
4 10 21
4 11 59
3 12 178
1 13 741
2 14 859
10 15 380
3 16 103
10 17 1
8 18 613
15 19 576

130965