Quân shipper

Quân làm shipper bán thời gian để kiếm thêm thu nhập. Một ngày nọ, Quân nhận được một đơn hàng đặc biệt từ CLB Tin học: giao hàng từ một phòng trọ bất kỳ đến một phòng khác, với yêu cầu là tổng quãng đường phải đúng bằng \(k\) mét.

Khu trọ mà Quân đang hoạt động được kết nối như một cây với \(n\) phòng và \(n - 1\) lối đi, lối đi thứ \(i\) có độ dài \(w_i\) mét.

Tuy nhiên, là một người hướng nội, Quân không thích phải đi qua nhiều nơi hoặc gặp quá nhiều người, nên dù giao hàng đúng yêu cầu \(k\) mét, Quân muốn chọn đường đi có ít lối đi nhất (ít cạnh nhất). Dĩ nhiên, Quân không đi vòng lại nơi đã đi, tức là hành trình phải là một đường đi đơn giữa hai phòng khác nhau.

Yêu cầu: Hãy giúp Quân tìm một đường đi trên cây sao cho tổng trọng số các cạnh trên đường đi đúng bằng \(k\) và trong số các đường thỏa mãn, đường đi được chọn có ít cạnh nhất. In ra số cạnh của đường đi đó; nếu không tồn tại đường đi nào như vậy, hãy in ra \(-1\).

Input

• Dòng đầu tiên chứa \(2\) số \(n, k\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le k \le 10^6\)).
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên \(u, v, w\) (\(1 \le u, v \le n\); \(0 \le w \le 10^6\)) mô tả một lối đi nối phòng \(u\) và phòng \(v\) có độ dài \(w\) mét.

Output

Số cạnh ít nhất của đường đi thỏa mãn có tổng trọng số bằng \(k\). Nếu không tồn tại đường đi thì in ra \(-1\).

Scoring

• Subtask 1: \(n, k \le 100\).
• Subtask 2: \(n \le 10^3\), \(k \le 10^6\).
• Subtask 3: \(n \le 2 \cdot 10^5\), \(k \le 100\).
• Subtask 4: \(n \le 2 \cdot 10^5\), \(k \le 10^6\).

Sample Input 1

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

Sample Output 1

2

Sample Input 2

3 3
1 2 1
2 3 1

Sample Output 2

-1