Đề bài

Mạng lưới đường bộ cao tốc của Cộng hòa Séc gồm \(N\) thành phố và \(N-1\) con đường có độ dài đã biết, tính bằng kilômét. Giữa mỗi cặp thành phố tồn tại đúng một đường đi. Ngoài ra, mỗi thành phố có đúng một trạm xăng và không có trạm xăng ở nơi nào khác.

Một ngày nọ, một số người quyết định đi du lịch bằng ô tô. Tổng cộng có \(N^2\) chiếc xe di chuyển. Điều kỳ lạ là với mỗi cặp thành phố có thứ tự \((a,b)\), có đúng một chiếc xe đi từ thành phố \(a\) đến thành phố \(b\) theo đường đi duy nhất giữa hai thành phố.

Vì mọi người ở Cộng hòa Séc đều dùng xe Škoda, mỗi xe có bình nhiên liệu cùng dung tích \(K\) lít và tiêu thụ đều đặn một lít xăng trên mỗi kilômét. Trước khi khởi hành, bình nhiên liệu của mỗi xe đều đầy. Người Séc cũng khá dễ đoán: vì lười, họ chỉ đổ xăng khi không còn đủ nhiên liệu để đến thành phố tiếp theo; xe được phép đến một thành phố với bình xăng rỗng. Khi buộc phải dừng ở một trạm xăng, họ luôn đổ đầy bình.

Cơ quan thuế Séc muốn biết trong ngày có bao nhiêu xe đã dừng tại từng trạm xăng. Dựa trên hành vi dễ đoán này, hãy tính các giá trị đó.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách, lần lượt là số thành phố và dung tích bình nhiên liệu của mỗi xe.

Mỗi dòng trong \(N-1\) dòng tiếp theo mô tả một con đường và chứa ba số nguyên \(u_i\), \(v_i\), \(l_i\), cách nhau bởi dấu cách. Hai số \(u_i\), \(v_i\) là chỉ số của hai thành phố được con đường thứ \(i\) nối với nhau, còn \(l_i\) là độ dài con đường tính bằng kilômét.

Các thành phố được đánh số từ \(0\) đến \(N-1\). Dữ liệu bảo đảm giữa mỗi cặp thành phố tồn tại đúng một đường đi.

Dữ liệu ra

In \(N\) dòng. Các dòng lần lượt chứa số xe dừng tại trạm xăng của thành phố \(0\), thành phố \(1\), ..., thành phố \(N-1\).

Giới hạn

• \(2\le N\le 70\,000\).
• \(1\le K\le 10^9\).
• \(0\le l_i\le K\) với mọi \(0\le i\le N-2\).

Chấm điểm

Gọi \(D\) là số con đường lớn nhất cùng nối với một thành phố.

• Subtask 1 (18 điểm): \(N\le 1\,000\) và \(K\le 1\,000\).
• Subtask 2 (8 điểm): \(D\le 2\) và \(l_i=1\) với mọi \(0\le i\le N-2\).
• Subtask 3 (10 điểm): \(D\le 2\).
• Subtask 4 (12 điểm): \(K\le 10\) và \(D\le 10\).
• Subtask 5 (17 điểm): \(K\le 10\).
• Subtask 6 (35 điểm): Không có ràng buộc bổ sung.

Ví dụ

3 1
0 1 1
1 2 1

0
2
0

6 2
0 1 1
1 2 1
2 3 1
3 4 2
4 5 1

0
3
3
12
8
0