题目描述

Yuki 有一棵包含 $n$ 个结点的树，每条边有一个边权 $w_i$，边权可能为负数。

定义 $\operatorname{dis}(u,v)$ 表示树上结点 $u$ 到结点 $v$ 的路径上的边权之和。

定义一个排列 $p_1,\dots,p_n$ 的价值为 $\sum\limits_{i=1}^{n}\operatorname{dis}(p_i,p_{i \bmod n+1})$，你需要求出所有 $1\sim n$ 的排列的最小价值。

输入格式

本题有多组测试数据。

输入的第一行包含两个正整数 $c,T$，分别表示测试点编号和测试数据组数。样例满足 $c=0$。

接下来依次输入每组测试数据。对于每组测试数据：

• 第一行包含一个正整数 $n$。
• 接下来 $n-1$ 行，第 $i$ 行包含三个正整数 $u_i,v_i,w_i$，表示树上有一条连接 $u_i,v_i$ 的权值为 $w_i$ 的边。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示所有 $1\sim n$ 的排列的最小价值。

样例 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

样例 1 输出

20
-50

样例 1 解释

• 对于第一组测试数据，其中一个价值最小的 $1\sim n$ 的排列为 $\{3,1,2,4,5\}$，它的价值为 $\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$。
• 对于第二组测试数据，其中一个价值最小的 $1\sim n$ 的排列为 $\{2,4,3,5,1,6,7\}$。

样例 2

见 lush/lush2.in 与 lush/lush2.ans。

样例 3

见 lush/lush3.in 与 lush/lush3.ans。

样例 4

见 lush/lush4.in 与 lush/lush4.ans。

样例 5

见 lush/lush5.in 与 lush/lush5.ans。

样例 6

见 lush/lush6.in 与 lush/lush6.ans。

样例 7

见 lush/lush7.in 与 lush/lush7.ans。

数据范围

对于所有测试数据，保证：

• $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$。