มีเมือง $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 |