Hay $n$ ciudades, numeradas de 1 a $n$. También hay $n - 1$ carreteras bidireccionales que conectan estas ciudades, de modo que para cada par de ciudades $x$ e $y$, existe un camino de $x$ a $y$. La $i$-ésima carretera conecta las ciudades $u_i$ y $v_i$, y tiene un costo $c_i$. Cada vez que pasas por la carretera $i$, gastas $c_i$ monedas.
Ahora estás en la ciudad 1 y quieres viajar para visitar todas las ciudades. Cada segundo, si estás en la ciudad $x$, puedes elegir una ciudad $y$ que esté conectada directamente con la ciudad $x$ mediante una carretera, moverte a la ciudad $y$ y pagar el costo de la carretera respectiva. Cada carretera se puede recorrer a lo sumo dos veces. Cuando hayas visitado todas las ciudades y estés en la ciudad 1, puedes terminar tu viaje. El costo del viaje es el costo total de todos los movimientos que realizaste.
También hay un entero $k$. Durante tu viaje, puedes usar un cupón gratuito una vez, haciendo que tus siguientes $k$ movimientos no tengan costo.
Para cada $k$ de 0 a $2n - 2$, debes calcular el costo mínimo de un viaje que visite todas las ciudades y utilice el cupón de manera óptima.
Entrada
La primera línea contiene un solo entero $t$ ($1 \le t \le 400$), el número de casos de prueba. Para cada caso de prueba:
La primera línea contiene un entero $n$ ($1 \le n \le 2000$), que denota el número de ciudades.
Las siguientes $n - 1$ líneas describen las carreteras. La $i$-ésima de estas líneas contiene tres enteros, $u_i$, $v_i$ y $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), que denotan las ciudades conectadas por la $i$-ésima carretera y el costo de esa carretera.
Existe un camino entre cualquier par de ciudades. La suma de $n$ no supera $2000$.
Salida
Para cada caso de prueba, imprime una línea con $2n - 1$ enteros: las respuestas para $k$ desde 0 hasta $2n - 2$.
Ejemplo
Entrada
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
Salida
18 15 12 10 8 5 3 2 0 32 27 22 21 17 13 12 8 4 3 2 1 0
Nota
En el primer caso de prueba, siempre podemos viajar a lo largo del camino $1, 2, 3, 2, 4, 5, 4, 2, 1$, con la secuencia de costos $2, 3, 3, 1, 3, 3, 1, 2$. Los segmentos sin costo para cada $k$ se muestran a continuación.
| $k$ | segmento sin costo | respuesta |
|---|---|---|
| 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 |