توجد $n$ مدن، مرقمة من 1 إلى $n$. وتوجد أيضاً $n - 1$ طرق ثنائية الاتجاه تربط بين هذه المدن، بحيث إنه لكل مدينتين $x$ و $y$ يوجد مسار من $x$ إلى $y$. يربط الطريق الـ $i$ بين المدينتين $u_i$ و $v_i$، وله تكلفة $c_i$. في كل مرة تمر فيها عبر الطريق $i$، تنفق $c_i$ عملة معدنية.
أنت الآن في المدينة 1 وتريد السفر لزيارة جميع المدن. في كل ثانية، إذا كنت في المدينة $x$، يمكنك اختيار مدينة $y$ متصلة مباشرة بالمدينة $x$ عبر طريق، والانتقال إلى المدينة $y$، ودفع تكلفة الطريق المقابل. يمكن المرور عبر كل طريق مرتين على الأكثر. عندما تكون قد زرت جميع المدن وأصبحت في المدينة 1، يمكنك إنهاء رحلتك. تكلفة الرحلة هي إجمالي تكلفة جميع التنقلات التي قمت بها.
يوجد أيضاً عدد صحيح $k$. أثناء رحلتك، يمكنك استخدام قسيمة مجانية مرة واحدة، مما يجعل تنقلاتك الـ $k$ التالية بلا تكلفة.
لكل $k$ من 0 إلى $2n - 2$، يجب عليك حساب أقل تكلفة لرحلة تزور جميع المدن وتستخدم القسيمة بشكل أمثل.
الإدخال
يحتوي السطر الأول على عدد صحيح واحد $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$ عدداً صحيحاً: الإجابات لكل $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 |