Universal Cup Judging System

Universal Cup

時間限制: 1 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

There are $n$ cities, numbered from 1 to $n$. There are also $n - 1$ bidirectional roads connecting these cities, so that for every two cities $x$ and $y$, there exists a path from $x$ to $y$. The $i$-th road connects cities $u_i$ and $v_i$, and has a cost $c_i$. Every time you pass through road $i$, you spend $c_i$ coins.

You are now at city 1 and want to travel to visit all cities. Every second, if you are at city $x$, you can choose a city $y$ that is directly connected with city $x$ by a road, move to city $y$, and pay the cost of the respective road. Each road can be passed at most twice. When you have visited all cities and are at city 1, you can finish your travel. The cost of the travel is the total cost of all the moves you made.

There is also an integer $k$. During your travel, you can use a free coupon once, making your following $k$ moves have no cost.

For every $k$ from 0 to $2n - 2$, you should calculate the minimum cost of a travel that visits all cities and uses the coupon optimally.

Input

The first line contains a single integer $t$ ($1 \le t \le 400$), the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 2000$), denoting the number of cities.

The next $n - 1$ lines describe the roads. The $i$-th of these lines contains three integers, $u_i$, $v_i$, and $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), denoting the cities connected by the $i$-th road and the cost of that road.

There is a path between any pair of cities. The sum of $n$ does not exceed $2000$.

Output

For each test case, output one line containing $2n - 1$ integers: the answers for $k$ from 0 to $2n - 2$.

Example

Input

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

Output

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

Note

In the first test case, we can always travel along the path $1, 2, 3, 2, 4, 5, 4, 2, 1$, with the cost sequence $2, 3, 3, 1, 3, 3, 1, 2$. The cost-free segments for each $k$ are shown below.

$k$ cost-free segment answer
0 $[]$ 18
1 $[3]$ 15
2 $[3, 3]$ 12
3 $[2, 3, 3]$ 10
4 $[3, 3, 1, 3]$ 8
5 $[3, 3, 1, 3, 3]$ 5
6 $[2, 3, 3, 1, 3, 3]$ 3
7 $[2, 3, 3, 1, 3, 3, 1]$ 2
8 $[2, 3, 3, 1, 3, 3, 1, 2]$ 0

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.