Весенний турнир 2011 - Московский метрополитен

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

задачи
видимые пробелы
простые формулы
широкий текст
редактор

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ s, u_i, v_i ≤ 13;

1 ≤ T, t_i ≤ 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`