Đua tốc độ

Kể từ khi IOI, thành phố Pattaya sẽ tổ chức cuộc đua Olympic quốc tế về đua tốc độ (IOR) 2011. Ban tổ chức phải tìm ra vòng đua tốt nhất cho cuộc thi này.

Ở vùng Pattaya - Chonburi, có \(N\) thành phố được nối với nhau bởi mạng gồm \(N-1\) đường cao tốc. Mỗi đường cao tốc đều cho phép đi theo cả hai chiều, nối hai thành phố phân biệt và có độ dài đo bằng kilomet là số nguyên. Ngoài ra, có đúng một đường đi giữa cặp hai thành phố bất kỳ, nghĩa là đây là một cấu trúc cây.

Cuộc thi IOR có quy tắc đặc biệt: một vòng đua phải có độ dài đúng \(K\) kilomet, bắt đầu và kết thúc ở hai thành phố phân biệt. Để tối ưu hóa việc tổ chức, vòng đua phải sử dụng ít đường cao tốc nhất có thể.

Yêu cầu: Bạn hãy cho biết số lượng đường cao tốc nhỏ nhất trên vòng đua hợp quy tắc có độ dài đúng \(K\). Nếu không tìm được vòng đua nào như vậy, kết quả sẽ là \(-1\).

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 2 \cdot 10^5\), \(1 \le K \le 10^9\)).
• \(N-1\) dòng tiếp theo, mỗi dòng ghi 3 số \(u, v, l\) (\(1 \le u, v \le N\)), với \(u\) và \(v\) là hai thành phố nối với nhau bằng một đường cao tốc có độ dài \(l\) (\(1 \le l \le 10^9\)).

Output

In ra một số nguyên duy nhất là kết quả của bài toán.

Example

4 3
0 1 1
1 2 2
1 3 4

2

3 3
0 1 1
1 2 1

-1

11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7

2

Scoring

• Subtask 1 (9 điểm): \(1 \le N \le 100, 1 \le K \le 100\). Đỉnh \(i\) sẽ nối đến đỉnh \(i + 1\).
• Subtask 2 (12 điểm): \(1 \le N \le 1000, 1 \le K \le 1000000\).
• Subtask 3 (22 điểm): \(1 \le N \le 200\,000, 1 \le K \le 100\).
• Subtask 4 (57 điểm): Không có giới hạn gì thêm.