Задача H. Московский метрополитен

Автор:И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Ровно 76 лет назад, 15 мая 1935 года, начал работу московский метрополитен. Первоначально он состоял из 13 станций.

Рассмотрим модель московского метрополитена, как набора из 13 станций, соединенных M туннелями. Никакой туннель не ведет из станции в нее же и никакая пара станций не может быть соединена более чем одним туннелем. Для каждого туннеля i известно ti — время проезда по нему. Движение поездов в туннелях двустороннее.

Тов. Сидоров находится на станции с номером s. У него выдалось T свободных минут и он решил прокатиться по станциям метрополитена. При этом, он хочет потратить на все переезды ровно T минут и вернуться на станцию s.

Определите, возможно ли это. Если да, то найдите последовательность номеров станций, которые должен посетить тов. Сидоров. Первым и последним числом в последовательности должен быть номер s.

Временем переходов между станциями и ожидания поездов следует пренебречь.

Формат входного файла

В первой строке входного файла содержатся целые числа M T s. Далее следует M строк с описанием туннелей. Каждый туннель описывается тремя целыми числами: двумя номерами станций, ui и vi, и временем ti.

Формат выходного файла

В первую строку выходного файла выведите слово "YES", если требуемый маршрут существует, и "NO" в противном случае. Если ответ существует, то в следующей строке выведите искомый маршрут. Если ответов несколько, выведите любой из них.

Ограничения

1 ≤ s, ui, vi ≤ 13;

1 ≤ T, ti ≤ 1000;

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 6 1
1 2 1
2 3 2
3 4 3
4 1 4
YES
1 2 3 2 1

0.041s 0.012s 15