กำหนดต้นไม้ที่มีจุดยอด $N$ จุดให้ จุดยอดมีหมายเลขเรียงตั้งแต่ $1$ ถึง $N$ เส้นเชื่อมที่ $i$ เชื่อมจุดยอด $A_i$ กับ $B_i$ และมีน้ำหนัก $C_i$ สำหรับ $1 \le i \le N-1$

ระยะเทเลพอร์ตระหว่างจุดยอดสองจุดในต้นไม้คือค่าน้ำหนักเส้นเชื่อมที่มากที่สุดบนเส้นทางสั้นที่สุดที่เชื่อมจุดทั้งสอง ระยะเทเลพอร์ตระหว่างจุดยอดกับตัวมันเองนิยามเป็น $0$

ผู้คนที่อาศัยอยู่บนต้นไม้ต้องการจัดการประชุม $N$ ครั้ง การประชุมที่ $i$ มีผู้เข้าร่วมเป็นผู้ที่อาศัยอยู่ในจุดยอดหมายเลขตั้งแต่ $1$ ถึง $i$ ปีนี้ เนื่องจากการระบาดของไวรัสโคโรนา ผู้เข้าประชุมจะเดินทางไปยังสถานที่ที่เลือกไว้ $X$ แห่ง แล้วเชื่อมต่อกันผ่านอินเทอร์เน็ตจากสถานที่เหล่านั้น

กล่าวอย่างเป็นทางการ สำหรับการประชุมแต่ละครั้ง เราจะเลือกจุดยอดที่แตกต่างกันทุกคู่ $X$ จุด $v_1,v_2,\ldots,v_X$ เมื่อกำหนดจุดยอดแล้ว แต่ละคนจะเคลื่อนไปยังจุดหนึ่งใน $v_1,\ldots,v_X$ ที่มีระยะเทเลพอร์ตจากตนน้อยที่สุด ให้นิยามค่าใช้จ่ายการประชุมสำหรับ $X$ และ $i$ ที่กำหนดเป็นระยะเทเลพอร์ตที่มากที่สุดในบรรดาผู้เข้าประชุม เราจะเลือกจุดยอด $v_1,\ldots,v_X$ ให้ค่าใช้จ่ายการประชุมน้อยที่สุดที่เป็นไปได้

ค่า $X$ ขึ้นอยู่กับสถานการณ์ไวรัสโคโรนา และอาจมีค่าตั้งแต่ $1$ ถึง $K$ เพื่อเตรียมการประชุมล่วงหน้า จงเขียนโปรแกรมที่หาผลรวมค่าใช้จ่ายการประชุมสำหรับค่า $X$ ที่เป็นไปได้ทั้งหมดตั้งแต่ $1$ ถึง $K$ รวมปลายทั้งสอง สำหรับการประชุมแต่ละครั้งใน $N$ ครั้ง

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็มสองจำนวน $N$ และ $K$ คือจำนวนจุดยอดและขอบเขตบนของ $X$ ตามลำดับ ($1 \le K \le N \le 3\cdot10^5$)

อีก $N-1$ บรรทัดถัดไปอธิบายต้นไม้ แต่ละบรรทัดมีจำนวนเต็มสามจำนวน $A_i,B_i,C_i$ ระบุว่ามีเส้นเชื่อมระหว่างจุดยอด $A_i$ กับ $B_i$ ที่มีน้ำหนัก $C_i$ ($1 \le A_i,B_i,C_i \le N$) รับประกันว่ากราฟที่ได้เป็นต้นไม้

ข้อมูลส่งออก

พิมพ์ $N$ บรรทัด ในบรรทัดที่ $i$ พิมพ์ผลรวมค่าใช้จ่ายของการประชุมที่ $i$ สำหรับ $X$ ทุกค่าตั้งแต่ $1$ ถึง $K$ รวมปลายทั้งสอง

ตัวอย่าง

ข้อมูลนำเข้า 1

10 4
5 1 2
1 6 4
6 2 1
2 8 9
8 3 5
3 4 8
4 10 9
10 9 8
9 7 7

ข้อมูลส่งออก 1

0
4
13
21
23
23
30
31
33
34

ข้อมูลนำเข้า 2

8 3
7 3 4
4 5 2
3 6 1
6 8 6
8 5 1
2 5 8
1 5 2

ข้อมูลส่งออก 2

0
8
14
16
16
16
18
18