eolymp
bolt
Try our new interface for solving problems

IOI

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 255 MiB

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

  1. Шлях складається з послiдовностi рiзних мiст a_1 , a_2 , . . . , a_k , таких, що мiж кожними двома сусiднiми мiстами повинно iснувати ребро.

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

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

Giriş verilənləri

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

Кожен з наступних n − 1 рядкiв мiстить три цiлi числа v_i , u_i та t_i(1 ≤ u_i , v_i ≤ n, v_i ≠ u_i , 1 ≤ t_i ≤ 10^6), що означає, що мiж мiстами v_i та u_i iснує дорога довжиною t_i .

Çıxış verilənləri

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

####Примiтка

  • У першому прикладi можна вибрати послiдовнiсть вершин 1, 2, 3.

  • У другому прикладi це зробити неможливо.

  • У третьому прикладi можна вибрати 11, 9, 7.

Nümunə

Giriş verilənləri #1
4 3
1 2 1
2 3 2
2 4 4
Çıxış verilənləri #1
3
Giriş verilənləri #2
3 3
1 2 1
2 3 1
Çıxış verilənləri #2
-1
Giriş verilənləri #3
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
Çıxış verilənləri #3
3