seuOJ474 - 归乡

准备好了吗，旅行者。

提瓦特大陆是一棵 $n$ 个节点的树，在大陆上 $u_i,v_i$ 两地距离 $w_i$ ，定义 $f(u,v)$ 大陆上 $u,v$ 两地之间的简单路径中任意相邻两地之间距离的最大值（一条边的最长长度），请你求出 $\sum_{u=1}^{n}\sum_{v=i+1}^{n} f(u,v)$ 。

树上简单路径是指树中的一条路径，从树的一个节点开始，经过不重复的节点——即没有再次经过已经访问过的节点——到达另一个点。换句话说，树上简单路径是一条不经过重复节点的路径，它连接了树中的两个节点，且路径上的节点都不会重复出现。

第一行，一个整数 $t(1\le t \le 10^4)$ ，代表数据组数。

对于每组数据：
第一行，一个整数 $n(1\le n \le 10^6)$ ，代表树的节点个数。
接下来的 $n-1$ 行，每行 $3$ 个整数 $u,v,w(1\le u,v \le n;1\le w \le 10^7)$ ，代表树上的一条边。

保证给出的数据构成一棵树，且同一测试点的 $n$ 的总和不超过 $10^6$ 。

对于每组数据，输出一行整数代表 $\sum_{i=1}^{n}\sum_{j=i+1}^{n} f(u,v)$ 的值。

输入样例

输出样例

66
9

提示
在样例的第 $2$ 组数据中， $f(1,2)=1$ 、 $f(1,3)=1$ 、 $f(1,4)=2$ 、 $f(2,3)=1$ 、 $f(2,4)=2$ 、 $f(3,4)=2$ ，所以最终答案为 $1+1+2+1+2+2=9$ 。