Yuki has a tree with $n$ nodes, where each edge has a weight $w_i$. The edge weights can be negative.

Let $\operatorname{dis}(u, v)$ denote the sum of edge weights on the path between node $u$ and node $v$ in the tree.

The value of a permutation $p_1, \dots, p_n$ is defined as $\sum\limits_{i=1}^{n}\operatorname{dis}(p_i, p_{i \bmod n+1})$. You need to find the minimum value among all permutations of $1 \sim n$.

Input

This problem contains multiple test cases.

The first line contains two positive integers $c$ and $T$, representing the test case ID and the number of test cases, respectively. The sample satisfies $c=0$.

Each test case is described as follows: - The first line contains a positive integer $n$. - The next $n-1$ lines each contain three integers $u_i, v_i, w_i$, representing an edge between $u_i$ and $v_i$ with weight $w_i$.

Output

For each test case, output a single line containing an integer representing the minimum value of the permutation.

Examples

Input 1

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

Output 1

20
-50

Note 1

• For the first test case, one of the permutations that achieves the minimum value is $\{3, 1, 2, 4, 5\}$. Its value is $\operatorname{dis}(3, 1) + \operatorname{dis}(1, 2) + \operatorname{dis}(2, 4) + \operatorname{dis}(4, 5) + \operatorname{dis}(5, 3) = 1 + 4 + 2 + 5 + 8 = 20$.
• For the second test case, one of the permutations that achieves the minimum value is $\{2, 4, 3, 5, 1, 6, 7\}$.

Examples 2-7

See lush/lush2.in and lush/lush2.ans through lush/lush7.in and lush/lush7.ans.

Constraints

For all test cases, it is guaranteed that:

• $1 \le T \le 3$;
• $2 \le n \le 2 \times 10^5$;
• $1 \le u_i, v_i \le n$, $-10^3 \le w_i \le 10^3$.