Description

在一棵有$n$个节点的树上，有$ {n} \over {2} $种晶蝶，每种晶蝶各有$2$只。同种晶蝶两两之间会相互吸引，它们会朝着彼此前进，最终在树上某点相遇。现在好奇心作祟的闯闯决定为难一下晶蝶们，闯闯可以随意安排每只晶蝶的位置，他想要使所有晶蝶走过的总路程和最大，请问这个总路程和最大会是多少？

Input Format

第一行输入一个正整数$t(1≤t≤10)$，表示共有$t$组测试样例。

接下来每组测试样例，第一行输入一个正整数$n(1≤n≤100000,$题目保证$n$是偶数$)$，接着有$n-1$行描述一棵树，每行包含三个正整数$u,v,w(1≤u,v≤n,0≤w≤10^9)$，表示有一条边权为$w$的边连接$u$和$v$两节点。

Output Format

对于每组测试样例，输出一行，包含一个正整数，表示总路程和的最大值。

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

16

Hint

对于题目样例，分别将$3$种晶蝶安排在$(1,3),(2,5),(4,6)$即可，这样可以得知答案为$16$。

Source

Online Judge http://127.0.0.1