Знайдiть шлях, для якого виконуються такi умови:
Шлях складається з послiдовностi рiзних мiст , , . . . , , таких, що мiж кожними двома сусiднiми мiстами повинно iснувати ребро.
Сумарна довжина шляху повинна бути рiвною .
Потрiбно вибрати таку послiдовнiсть мiст, що k — мiнiмальне.
Перший рядок мiстить два цiлi числа та — кiлькiсть мiст та потрiбна довжина.
Кожен з наступних рядкiв мiстить три цiлi числа , та (), що означає, що мiж мiстами та iснує дорога довжиною .
Виведiть мiнiмальне , або , якщо такого шляху немає.
####Примiтка
У першому прикладi можна вибрати послiдовнiсть вершин .
У другому прикладi це зробити неможливо.
У третьому прикладi можна вибрати .