1부터 $n$까지 번호가 매겨진 $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$번째 줄에는 $i$번째 도로가 연결하는 두 도시와 그 도로의 비용을 나타내는 세 정수 $u_i$, $v_i$, $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$)가 주어집니다.
임의의 두 도시 사이에는 경로가 존재합니다. 모든 테스트 케이스에서 $n$의 합은 $2000$을 초과하지 않습니다.
출력
각 테스트 케이스마다 한 줄에 $2n - 1$개의 정수를 출력합니다: 이는 $k$가 0부터 $2n - 2$까지일 때의 답입니다.
예제
입력
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
출력
18 15 12 10 8 5 3 2 0 32 27 22 21 17 13 12 8 4 3 2 1 0
노트
첫 번째 테스트 케이스에서는 항상 경로 $1, 2, 3, 2, 4, 5, 4, 2, 1$을 따라 여행할 수 있으며, 이때의 비용 수열은 $2, 3, 3, 1, 3, 3, 1, 2$입니다. 각 $k$에 대한 무료 구간은 아래와 같습니다.
| $k$ | 무료 구간 | 답 |
|---|---|---|
| 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 |