Cho một cây gồm $N$ đỉnh. Các đỉnh được đánh số thứ tự từ 1 đến $N$. Cạnh thứ $i$ nối hai đỉnh $A_i$ và $B_i$ với trọng số $C_i$, với $1 \le i \le N - 1$.

Khoảng cách dịch chuyển (teleport distance) giữa hai đỉnh bất kỳ trên cây là trọng số lớn nhất của một cạnh nằm trên đường đi ngắn nhất nối hai đỉnh đó. Khoảng cách dịch chuyển giữa một đỉnh và chính nó được định nghĩa là 0.

Những người sống trên cây muốn tổ chức $N$ cuộc họp. Cuộc họp thứ $i$ có sự tham gia của những người sống tại các đỉnh được đánh số từ 1 đến $i$. Năm nay, do sự lây lan của virus corona, những người tham gia cuộc họp sẽ đến $X$ địa điểm được chọn, sau đó kết nối qua Internet từ các địa điểm này.

Cụ thể hơn, với mỗi cuộc họp, chúng ta sẽ chọn $X$ đỉnh phân biệt $v_1, v_2, \dots, v_X$. Khi các đỉnh đã được xác định, mỗi người sẽ di chuyển đến một trong các đỉnh $v_1, \dots, v_X$ có khoảng cách dịch chuyển đến đỉnh đó là nhỏ nhất. Chúng ta định nghĩa chi phí cuộc họp cho $X$ và $i$ đã cho là giá trị lớn nhất trong các khoảng cách dịch chuyển của những người tham gia cuộc họp. Chúng ta sẽ chọn các đỉnh $v_1, \dots, v_X$ sao cho chi phí cuộc họp là nhỏ nhất có thể.

Giá trị của $X$ phụ thuộc vào tình hình dịch bệnh và có thể thay đổi từ 1 đến $K$. Để chuẩn bị trước cho cuộc họp, hãy viết chương trình tính tổng chi phí cuộc họp cho tất cả các giá trị $X$ từ 1 đến $K$ (bao gồm cả hai đầu) cho mỗi cuộc họp trong số $N$ cuộc họp.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $K$: số lượng đỉnh và giới hạn trên của $X$ ($1 \le K \le N \le 3 \cdot 10^5$).

$N - 1$ dòng tiếp theo mô tả cây. Mỗi dòng chứa ba số nguyên $A_i, B_i$ và $C_i$, cho biết có một cạnh nối giữa hai đỉnh $A_i$ và $B_i$ với trọng số $C_i$ ($1 \le A_i, B_i, C_i \le N$). Đảm bảo rằng đồ thị thu được là một cây.

Dữ liệu ra

In ra $N$ dòng. Trên dòng thứ $i$, in ra tổng chi phí cuộc họp của cuộc họp thứ $i$ cho tất cả các giá trị $X$ từ 1 đến $K$ (bao gồm cả hai đầu).

Ví dụ

Ví dụ 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

0
4
13
21
23
23
30
31
33
34

Ví dụ 2

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

0
8
14
16
16
16
18
18