C. Путешествие
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Ирина поехала отдыхать в один из самых известных городов Берляндии — город Берлятов. В городе находится n достопримечательностей, пронумерованных от 1 до n, некоторые из которых соединены односторонними дорогами. Дороги в Берлятове устроены так, что циклических маршрутов между достопримечательностями не существует.

Изначально Ирина находится у достопримечательности 1, а конечный пункт её путешествия — достопримечательность n. Естественно, Ирина хочет посетить как можно больше достопримечательностей во время своего путешествия. Однако, время пребывания Ирины в Берлятове ограничено, и она может пробыть там не больше T единиц времени.

Помогите Ирине определить, какое наибольшее количество достопримечательностей она сможет посетить на своём пути от достопримечательности 1 до достопримечательности n за время, не превышающее T. Гарантируется, что существует хотя бы один маршрут от достопримечательности 1 до достопримечательности n, на прохождение которого Ирина потратит не более T единиц времени.

Входные данные

В первой строке входных данных находятся три целых числа n, m и T (2 ≤ n ≤ 5000,  1 ≤ m ≤ 5000,  1 ≤ T ≤ 109) — количество достопримечательностей, количество дорог между ними и время пребывания Ирины в Берлятове соответственно.

Следующие m строк описывают дороги в Берлятове. i-я из них содержит 3 целых числа ui, vi, ti (1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ ti ≤ 109), означающая, что существует дорога, ведущая от достопримечательности ui к достопримечательности vi, прохождение которой занимает у Ирины ti единиц времени. Гарантируется, что дороги не образуют циклических маршрутов.

Гарантируется, что между любыми двумя достопримечательностями существует не более одной дороги.

Выходные данные

В первой строке выведите единственное целое число k (2 ≤ k ≤ n) — максимальное количество достопримечательностей, которые Ирина сможет посетить во время своего путешествия от достопримечательности 1 к достопримечательности n за время, не превышающее T.

Во второй строке выведите k различных целых чисел — номера достопримечательностей, которые посетит Ирина на своем пути, в порядке их посещения.

Если ответов несколько, выведите любой.

Примеры
Входные данные
4 3 13
1 2 5
2 3 7
2 4 8
Выходные данные
3
1 2 4
Входные данные
6 6 7
1 2 2
1 3 3
3 6 3
2 4 2
4 6 2
6 5 1
Выходные данные
4
1 2 4 6
Входные данные
5 5 6
1 3 3
3 5 3
1 2 2
2 4 3
4 5 2
Выходные данные
3
1 3 5