树上两点间距离之和

题目描述

给定一棵树,计算树中任意两个节点之间的总距离。 树中任意两个顶点之间的总距离为 $d_{01}+d_{02}+d_{03}+d_{04}+d_{12}+d_{13}+d_{14}+d_{23}+d_{24}+d_{34}= 6+3+7+9+9+13+15+10+12+2 = 86 $ ![](https://cdn.luogu.com.cn/upload/image_hosting/bas54ocz.png)

输入输出格式

输入格式


输出格式


第一行一个整数$ n (2 \le n \le 10^6)$:代表树中的节点数。节点编号从 0 到 n - 1。 接下来 n - 1 行,每行包含三个整数$ a (0 \le a < n)、b (0 \le b < n) 和 d (1 \le d \le 10),$表示在编号为$ a $和$ b $的节点之间存在一条长度为$ d $的边。

输入输出样例

输入样例 #1

5
0 1 6
0 2 3
0 3 7
3 4 2

输出样例 #1

86