Знайдіть шлях, для якого виконуються такі умови:

1. Шлях складається з послідовності різних міст a1 , a2 , . . . , ak , таких, що між кожними двома

сусідніми містами повинно існувати ребро.

2. Сумарна довжина шляху повинна бути рівною L.

Потрібно вибрати таку послідовність міст, що k — мінімальне.

Вхідні дані

Перший рядок містить два цілих числа n та l(1≤n≤2·10^5,1≤L≤10^6) — кількість міст та потрібна

довжина.

Кожен з наступних n−1 рядків містить три цілі числа vi , ui та ti (1≤ui,vi≤n,vi≠ui,1≤ti≤10^6), що

означає, що між містами vi та ui існує дорога довжиною ti .

Вихідні дані

Виведіть мінімальне k, або −1, якщо такого шляху немає

islamsalpagaro    3   11.12.2021 13:02    0