Дано дерево з $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