F. 世界如此可爱
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

幻想乡需要布置一个覆盖全境的灵力结界。灵梦发现，各结界节点构成的灵力网络是一棵带权无根树，边代表灵力通路，初始权值为自然灵力。为了稳定结界，灵梦需选择一个节点作为核心，并调整通路的灵力值，使得从核心到所有叶子结界点的灵力总和相同。灵梦可以往任意通路中注入额外灵力（非负值），求她所需消耗的最小灵力总和。

简要题面： 给定一棵包含 $$$n$$$ 个节点的带权无根树，你可以选择任意一个节点作为根，并通过在边添加非负权值，使得所有从根节点到叶子节点的路径权值和相等。求最少需要添加的权值总和。

选择 $$$u$$$ 为根的时候叶子定义为所有度数为 $$$1$$$ 的不为根的点。

Input

第一行包含一个整数 $$$T$$$ ( $$$1 \le T \le 1000$$$ ) 表示测试用例数。

每个测试用例的第一行包含一个正整数$$$n$$$ $$$(1 \le n \le 10^5)$$$，表示节点的个数。

接下来 $$$n−1$$$ 行，每行三个整数 $$$a_i$$$，$$$b_i$$$，$$$w_i$$$ $$$(1 \le w_i \le 10^9)$$$。表示一条从$$$a_i$$$连向$$$b_i$$$权值为$$$w_i$$$的边。

所有测试用例中保证 $$$n$$$ 的总和不超过 $$$2 \times 10^5$$$ 。

Output

仅包含一个整数，为最少添加的边权值。

Example
Input
2
7
6 3 71
2 1 59
3 1 66
4 2 70
7 4 34
5 1 84
13
13 10 3
3 1 53
5 4 83
6 3 93
11 2 40
7 5 83
4 1 34
9 7 79
8 2 47
2 1 4
10 9 61
12 6 8
Output
26
110