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

Первая строка ввода содержит целые числа M, N и S — число городов, число дорог и длину маршрута соответственно (1 ≤ M ≤ 100; 1 ≤ N ≤ 10 000; 1 ≤ S ≤ 2 · 10⁶).

Следующие N строк описывают дороги тройками целых чисел P, Q, R, где P и Q — номера городов, соединённых дорогой (1 ≤ P, Q ≤ M), а R — длина этой дороги (1 ≤ R ≤ 32 000).

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