Bạn được cho một cây $T$ gồm $N$ đỉnh. Mỗi cạnh có một trọng số là số nguyên dương.

Bạn có thể thực hiện thao tác sau trên cây đã cho: * Xóa một cạnh khỏi đồ thị, sau đó thêm một cạnh mới giữa hai đỉnh bất kỳ. Trọng số của cạnh mới phải bằng trọng số của cạnh đã xóa. Đồ thị thu được không nhất thiết phải là một cây.

Chúng ta định nghĩa trọng số của một đường đi là tổng trọng số của các cạnh trên đường đi đó. Khoảng cách giữa hai đỉnh $u$ và $v$ được định nghĩa là trọng số của đường đi ngắn nhất từ $u$ đến $v$ (đường đi có tổng trọng số nhỏ nhất). Nếu không tồn tại đường đi, khoảng cách được định nghĩa là $0$.

Trọng số của một đồ thị là giá trị lớn nhất trong các khoảng cách giữa mọi cặp đỉnh.

Nhiệm vụ của bạn là tìm trọng số lớn nhất của đồ thị có thể đạt được bằng cách thực hiện thao tác đúng $i$ lần, với $i = 0, 1, \dots, K$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách $N$ và $K$.

Dòng thứ $i$ trong số $N - 1$ dòng tiếp theo chứa ba số nguyên cách nhau bởi dấu cách $u_i$, $v_i$, và $w_i$, biểu diễn một cạnh vô hướng nối hai đỉnh khác nhau $u_i$ và $v_i$ với trọng số $w_i$.

Đảm bảo rằng các cạnh tạo thành một cây.

• $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$)

Dữ liệu ra

In ra $K + 1$ số nguyên cách nhau bởi dấu cách. Số nguyên thứ $i$ phải bằng trọng số lớn nhất của đồ thị có thể đạt được bằng cách thực hiện thao tác đúng $i - 1$ lần.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

14 16

Dữ liệu vào 2

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

Dữ liệu ra 2

13 20 21