لديك شجرة تضم $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$. للاستعداد للاجتماعات مسبقًا، اكتب برنامجًا يجد لكل اجتماع من الاجتماعات الـ $N$ مجموع تكاليف الاجتماع لجميع قيم $X$ الممكنة من $1$ إلى $K$ شاملًا.

الإدخال

يحتوي السطر الأول من الإدخال على عددين صحيحين $N$ و$K$: عدد الرؤوس والحد الأعلى لـ $X$، على الترتيب ($1\le K\le N\le3\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