准备好了吗，旅行者。
提瓦特大陆是一棵 nnn 个节点的树，在大陆上 ui,viu_i,v_iui,vi 两地距离 wiw_iwi，定义 f(u,v)f(u,v)f(u,v) 大陆上 u,vu,vu,v 两地之间的简单路径中任意相邻两地之间距离的最大值（一条边的最长长度），请你求出 ∑u=1n∑v=i+1nf(u,v)\sum_{u=1}^{n}\sum_{v=i+1}^{n} f(u,v)∑u=1n∑v=i+1nf(u,v)。
树上简单路径是指树中的一条路径，从树的一个节点开始，经过不重复的节点——即没有再次经过已经访问过的节点——到达另一个点。换句话说，树上简单路径是一条不经过重复节点的路径，它连接了树中的两个节点，且路径上的节点都不会重复出现。
第一行，一个整数 t(1≤t≤104)t(1\le t \le 10^4)t(1≤t≤104)，代表数据组数。
对于每组数据： 第一行，一个整数 n(1≤n≤106)n(1\le n \le 10^6)n(1≤n≤106)，代表树的节点个数。 接下来的 n−1n-1n−1 行，每行 333 个整数 u,v,w(1≤u,v≤n;1≤w≤107)u,v,w(1\le u,v \le n;1\le w \le 10^7)u,v,w(1≤u,v≤n;1≤w≤107)，代表树上的一条边。
保证给出的数据构成一棵树，且同一测试点的 nnn 的总和不超过 10610^6106。
对于每组数据，输出一行整数代表 ∑i=1n∑j=i+1nf(u,v)\sum_{i=1}^{n}\sum_{j=i+1}^{n} f(u,v)∑i=1n∑j=i+1nf(u,v) 的值。
输入样例
2 6 1 2 3 3 1 4 2 5 2 2 4 7 1 6 1 4 1 2 1 1 3 1 1 4 2
输出样例
66 9
提示 在样例的第 222 组数据中，f(1,2)=1f(1,2)=1f(1,2)=1、f(1,3)=1f(1,3)=1f(1,3)=1、f(1,4)=2f(1,4)=2f(1,4)=2、f(2,3)=1f(2,3)=1f(2,3)=1、f(2,4)=2f(2,4)=2f(2,4)=2、f(3,4)=2f(3,4)=2f(3,4)=2，所以最终答案为 1+1+2+1+2+2=91+1+2+1+2+2=91+1+2+1+2+2=9。
