Cho một cây gồm ~N~ đỉnh và ~N-1~ cạnh có trọng số. Các cạnh được đánh số từ 1 đến ~N-1~, cạnh thứ ~i~ nối cặp đỉnh ~(u, v)~ có trọng số ~c~.

Chi phí đường đi giữa hai đỉnh ~(u, v)~ là tổng trọng số các cạnh trên đường đi từ ~u~ đến ~v~ (~u \ne v~). Nếu không tồn tại đường đi từ ~u~ đến ~v~ thì chi phí đường đi giữa cặp đỉnh ~(u, v)~ là 0.

Một cách xóa cạnh được mô tả như sau:

• Chọn hai số nguyên dương ~L, R~ thoả mãn ~1 \le L \le R \le N-1~;

• Xóa tất cả các cạnh được đánh số từ ~L~ đến ~R~.

Cho trước một số nguyên dương ~K~. Một cách xóa cạnh được gọi là "đẹp" nếu mọi chi phí đường đi giữa cặp đỉnh bất kỳ không vượt quá ~K~. Hai cách xóa cạnh được coi là khác nhau khi có một cạnh trong cách xóa này không có trong cách xóa kia.

Yêu cầu: Đếm số lượng cách xóa cạnh được gọi là "đẹp".

Input

Dòng đầu tiên gồm hai số nguyên ~N, K~ (~1 \le N \le 10^5~; ~1 \le K \le 10^9~).

~N-1~ dòng sau, mỗi dòng gồm ba số nguyên ~u, v, c~ mô tả cạnh nối đỉnh ~u~ và đỉnh ~v~, có trọng số là ~c~ (~1 \le u, v \le N~; ~1 \le c \le 10^6~).

Output

Một số nguyên duy nhất là số lượng cách xóa cạnh được gọi là "đẹp".

Scoring

Sample Input 1

6 12
1 2 3
1 4 5
2 3 6
2 5 4
3 6 9

Sample Output 1

9

Notes

Có 9 cách xóa cạnh "đẹp" được mô tả chi tiết:

• ~L=1, R=1~: Xóa cạnh 1. Đây không phải là cách xóa cạnh "đẹp" vì tồn tại trọng số đường đi từ đỉnh 2 đến đỉnh 6 là 15 lớn hơn ~K=12~.

• ~L=1, R=2~: Xóa cạnh 1, 2. Đây không phải là cách xóa cạnh "đẹp" vì tồn tại trọng số đường đi từ đỉnh 2 đến đỉnh 6 là 15 lớn hơn ~K=12~.

• ~L=1, R=3~: Xóa cạnh 1, 2, 3. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 3 đến đỉnh 6 là 9 không vượt quá ~K=12~.

• ~L=1, R=4~: Xóa cạnh 1, 2, 3, 4. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 3 đến đỉnh 6 là 9 không vượt quá ~K=12~.

• ~L=1, R=5~: Xóa cạnh 1, 2, 3, 4, 5. Đây là cách xóa cạnh "đẹp" vì không tồn tại đường đi giữa mọi cặp đỉnh.

• ~L=2, R=2~: Xóa cạnh 2. Đây không phải là cách xóa cạnh "đẹp" vì tồn tại trọng số đường đi từ đỉnh 5 đến đỉnh 6 là 19 lớn hơn ~K=12~.

• ~L=2, R=3~: Xóa cạnh 2, 3. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 3 đến đỉnh 6 là 9 không vượt quá ~K=12~.

• ~L=2, R=4~: Xóa cạnh 2, 3, 4. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 3 đến đỉnh 6 là 9 không vượt quá ~K=12~.

• ~L=2, R=5~: Xóa cạnh 2, 3, 4, 5. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 1 đến đỉnh 2 là 3 không vượt quá ~K=12~.

• ~L=3, R=3~: Xóa cạnh 3. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 4 đến đỉnh 5 là 12 không vượt quá ~K=12~.

• ~L=3, R=4~: Xóa cạnh 3, 4. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 3 đến đỉnh 6 là 9 không vượt quá ~K=12~.

• ~L=3, R=5~: Xóa cạnh 3, 4, 5. Đây là cách xóa cạnh "đẹp" vì trọng số đường đi lớn nhất là đường đi từ đỉnh 2 đến đỉnh 4 là 8 không vượt quá ~K=12~.

• ~L=4, R=4~: Xóa cạnh 4. Đây không phải là cách xóa cạnh "đẹp" vì tồn tại trọng số đường đi từ đỉnh 4 đến đỉnh 6 là 23 lớn hơn ~K=12~.

• ~L=4, R=5~: Xóa cạnh 4, 5. Đây không phải là cách xóa cạnh "đẹp" vì tồn tại trọng số đường đi từ đỉnh 3 đến đỉnh 4 là 14 lớn hơn ~K=12~.

• ~L=5, R=5~: Xóa cạnh 5. Đây không phải là cách xóa cạnh "đẹp" vì tồn tại trọng số đường đi từ đỉnh 3 đến đỉnh 4 là 14 lớn hơn ~K=12~.