Sau khi thử nghiệm thành công với hệ thống trạm xạc tự động, công ty VinFast tiếp tục các thử nghiệm tự động khác. Hệ thống trạm xạc được mô hình hóa thành một đơn đồ thị vô hướng liên thông có trọng số gồm ~n~ đỉnh (là các trạm xạc được đánh số từ ~0~ đến ~n-1~), ~n-1~ cạnh và trọng số ~w_{u,v}~ là khoảng cách nối trực tiếp giữa trạm xạc ~u~ đến trạm xạc ~v~ ~(0 \le u,v \le n-1)~. Một xe điện đang có mức năng lượng ~k~ chỉ có thể di chuyển từ trạm xạc ~u~ đến trạm xạc ~v~ nếu hai trạm sạc nối trực tiếp với nhau và ~k \ge w_{u,v}~, khi đó xe sẽ mất ~w_{u,v}~ năng lượng.

Công ty đang thử nghiệm hệ thống tính số lần xạc tại các trạm xạc. Một thử nghiệm ~(u,v)~ được thực hiện như sau: Đặt một xe điện tại trạm xạc ~u~ nạp đầy mức năng lượng ~k~ cho xe di chuyển đến trạm xạc ~v~, quá trình di chuyển xe chỉ đi dọc theo tuyến đường duy nhất nối hai trạm xạc. Xe điện chỉ xạc khi không đủ mức năng lượng để đi đến trạm xạc tiếp theo. Một khi buộc phải dừng lại tại trạm xạc, xe sẽ được nạp đầy mức năng lượng ~k~ và trạm này được tính một lần xạc. Như vậy với ~n~ trạm xạc sẽ có tổng cộng tất cả ~n \cdot (n-1)~ thử nghiệm.

Yêu cầu: Hãy tính số lần xạc của từng trạm xạc sau khi thực hiện tất cả các lần thử nghiệm.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ ~(2 \le n \le 7 \cdot 10^4)~ và ~k~ ~(1 \le k \le 10^9)~ lần lượt là số lượng trạm xạc và mức năng lượng của xe thử nghiệm.

• ~n-1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u,v~ và ~w~ ~(0 \le w \le k)~, trong đó ~u~ và ~v~ là chỉ số của các trạm xạc được nối trực tiếp với nhau có trọng số ~w~.

Đảm bảo rằng giữa mỗi cặp trạm xạc luôn tồn tại duy nhất một đường đi.

Output

Gồm ~n~ dòng, chứa số lượng xe dừng lại tại trạm xạc để nạp năng lượng, theo thứ tự từ trạm xạc ~0~ đến trạm xạc ~n-1~.

Scoring

Gọi ~D~ là số lượng tối đa đường nối trực tiếp tới một trạm xạc.

Sample Input 1

3 1
0 1 1
1 2 1

Sample Output 1

0
2
0

Sample Input 2

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

Sample Output 2

0
3
3
12
8
0

Notes

Trong ví dụ thứ nhất, có ~3~ trạm xạc nằm trên một đường thẳng được nối với nhau bởi các đường có chiều dài ~1~ và xe thử nghiệm có mức năng lượng là ~1~. Chỉ có xe đi giữa hai trạm xạc ở hai đầu (từ ~0~ đến ~2~ và từ ~2~ đến ~0~) mới phải dừng lại nạp năng lượng tại trạm xạc ở giữa (trạm xạc ~1~).

Trong ví dụ thứ hai, có ~6~ trạm xạc nằm trên một đường thẳng và xe thử nghiệm có mức năng lượng là ~2~. Rất nhiều lượt xe cần phải dừng lại ở trạm xạc ~3~ và trạm xạc ~4~. Điều này hợp lý vì trạm xạc ~3~ và ~4~ được nối với nhau bằng đường nối có trọng số ~2~.