נתון עץ בעל $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 \le 3 \cdot 10^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