Es gibt $n$ Städte, die von 1 bis $n$ nummeriert sind. Außerdem gibt es $n - 1$ bidirektionale Straßen, die diese Städte verbinden, sodass für je zwei Städte $x$ und $y$ ein Pfad von $x$ nach $y$ existiert. Die $i$-te Straße verbindet die Städte $u_i$ und $v_i$ und hat Kosten $c_i$. Jedes Mal, wenn Sie die Straße $i$ passieren, geben Sie $c_i$ Münzen aus.
Sie befinden sich nun in Stadt 1 und möchten reisen, um alle Städte zu besuchen. Jede Sekunde können Sie, wenn Sie sich in Stadt $x$ befinden, eine Stadt $y$ wählen, die direkt über eine Straße mit Stadt $x$ verbunden ist, sich nach Stadt $y$ bewegen und die Kosten der jeweiligen Straße bezahlen. Jede Straße darf höchstens zweimal passiert werden. Wenn Sie alle Städte besucht haben und sich wieder in Stadt 1 befinden, können Sie Ihre Reise beenden. Die Kosten der Reise sind die Gesamtkosten aller von Ihnen durchgeführten Züge.
Es gibt außerdem eine ganze Zahl $k$. Während Ihrer Reise können Sie einmalig einen Gratis-Gutschein einsetzen, wodurch Ihre nächsten $k$ Züge kostenlos sind.
Für jedes $k$ von 0 bis $2n - 2$ sollen Sie die minimalen Kosten einer Reise berechnen, die alle Städte besucht und den Gutschein optimal nutzt.
Eingabe
Die erste Zeile enthält eine einzelne ganze Zahl $t$ ($1 \le t \le 400$), die Anzahl der Testfälle. Für jeden Testfall gilt:
Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 2000$), die die Anzahl der Städte angibt.
Die nächsten $n - 1$ Zeilen beschreiben die Straßen. Die $i$-te dieser Zeilen enthält drei ganze Zahlen, $u_i$, $v_i$ und $c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i \le 10^9$), die die durch die $i$-te Straße verbundenen Städte und die Kosten dieser Straße angeben.
Zwischen jedem Paar von Städten gibt es einen Pfad. Die Summe von $n$ überschreitet $2000$ nicht.
Ausgabe
Geben Sie für jeden Testfall eine Zeile mit $2n - 1$ ganzen Zahlen aus: die Antworten für $k$ von 0 bis $2n - 2$.
Beispiel
Eingabe
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
Ausgabe
18 15 12 10 8 5 3 2 0 32 27 22 21 17 13 12 8 4 3 2 1 0
Hinweis
Im ersten Testfall können wir immer entlang des Pfades $1, 2, 3, 2, 4, 5, 4, 2, 1$ mit der Kostenfolge $2, 3, 3, 1, 3, 3, 1, 2$ reisen. Die kostenlosen Abschnitte für jedes $k$ sind unten dargestellt.
| $k$ | kostenloser Abschnitt | Antwort |
|---|---|---|
| 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 |