有 $n$ 座城市，编号从 $1$ 到 $n$。还有 $n - 1$ 条双向道路连接这些城市，使得对于任意两座城市 $x$ 和 $y$，都存在一条从 $x$ 到 $y$ 的路径。第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，其花费为 $c_i$。每次经过第 $i$ 条道路时，你需要花费 $c_i$ 枚硬币。

你现在在城市 $1$，想要旅行访问所有的城市。每一秒，如果你在城市 $x$，你可以选择一座通过道路与城市 $x$ 直接相连的城市 $y$，移动到城市 $y$，并支付相应道路的花费。每条道路最多只能经过两次。当你访问了所有城市并且回到城市 $1$ 时，你可以结束你的旅行。旅行的花费是你进行的所有移动的花费总和。

还有一个整数 $k$。在你的旅行中，你可以使用一次免费优惠券，使你接下来的 $k$ 次移动没有花费。

对于从 $0$ 到 $2n - 2$ 的每个 $k$，你应该计算访问所有城市并最优地使用优惠券的旅行的最小花费。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 400$)，表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 2000$)，表示城市的数量。

接下来的 $n - 1$ 行描述道路。这些行中的第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $c_i$ ($1 \le u_i, v_i \le n$，$0 \le c_i \le 10^9$)，表示第 $i$ 条道路连接的城市以及该道路的花费。

任意两座城市之间都存在路径。$n$ 的总和不超过 $2000$。

输出格式

对于每个测试用例，输出一行，包含 $2n - 1$ 个整数：对于从 $0$ 到 $2n - 2$ 的每个 $k$ 的答案。

样例

输入样例 1

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

输出样例 1

18 15 12 10 8 5 3 2 0
32 27 22 21 17 13 12 8 4 3 2 1 0

说明 1

在第一个测试用例中，我们总是可以沿着路径 $1, 2, 3, 2, 4, 5, 4, 2, 1$ 旅行，其花费序列为 $2, 3, 3, 1, 3, 3, 1, 2$。对于每个 $k$ 的免花费线段如下所示。