ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC, Центральный подрегион, Рыбинск, октябрь 2002

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

D. Чемпионат по ралли

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Скоро пройдёт международный чемпионат по ралли. Согласно правилам соревнование проводится на обычных дорогах, а маршрут имеет фиксированную длину. Вам дана карта городов и двусторонних дорог, соединяющих их. Чтобы сделать соревнование безопасным, все дороги, по которым оно проходит, используются как односторонние. Соревнование может начаться и закончиться в любом месте дороги. Определите, возможно ли выбрать путь заданной длины S.

Исходные данные

Первая строка ввода содержит целые числа M, N и S — число городов, число дорог и длину маршрута соответственно (1 ≤ M ≤ 100; 1 ≤ N ≤ 10 000; 1 ≤ S ≤ 2 · 106).
Следующие N строк описывают дороги тройками целых чисел P, Q, R, где P и Q — номера городов, соединённых дорогой (1 ≤ P, QM), а R — длина этой дороги (1 ≤ R ≤ 32 000).

Результат

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

Примеры

исходные данныерезультат
3 2 20
1 2 10
2 3 5
NO
3 3 1000
1 2 1
2 3 1
1 3 1
YES
Источник задачи: Четвертьфинальные соревнования ACM ICPC 2002–2003 в центральном регионе России, Рыбинск, октябрь 2002
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1227. Чемпионат по ралли