Вам дано дерево $T$, состоящее из $N$ вершин. Каждое ребро имеет положительный целочисленный вес.

Вы можете выполнять следующую операцию над данным деревом: * Удалить ребро из графа, а затем добавить новое ребро между любыми двумя различными вершинами. Вес нового ребра должен быть таким же, как вес удаленного ребра. Полученный граф не обязательно должен быть деревом.

Мы определяем вес пути как сумму весов ребер на этом пути. Расстояние между двумя вершинами $u$ и $v$ определяется как вес кратчайшего пути от $u$ до $v$ (пути с минимальным весом). Если такого пути не существует, мы считаем расстояние равным 0.

Вес графа — это максимум расстояний между любыми двумя вершинами.

Ваша задача — найти наибольший вес графа, который можно получить, выполнив операцию ровно $i$ раз, для всех $i = 0, 1, \dots, K$.

Входные данные

Первая строка содержит два целых числа, разделенных пробелом: $N$ и $K$.

Следующие $N - 1$ строк содержат по три целых числа, разделенных пробелом: $u_i$, $v_i$ и $w_i$, представляющих неориентированное ребро, соединяющее две различные вершины $u_i$ и $v_i$ с весом $w_i$.

Гарантируется, что ребра образуют дерево.

• $2 \le N \le 2000$
• $0 \le K \le 2000$
• $1 \le u_i < v_i \le N$ ($1 \le i \le N - 1$)
• $1 \le w_i \le 10^9$ ($1 \le i \le N - 1$)

Выходные данные

Выведите $K + 1$ целое число, разделенных пробелом. $i$-е число должно быть равно наибольшему весу графа, который можно получить, выполнив операцию ровно $i - 1$ раз.

Примеры

Входные данные 1

5 1
1 3 2
4 5 4
3 4 3
2 3 7

Выходные данные 1

14 16

Входные данные 2

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

Выходные данные 2

13 20 21