| Автор: | Кулак Иван, Шелевой Ярослав, Артем Иващенко | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 64 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 1 |
Каждую пятницу Венечка садится на поезд с Курского вокзала и едет до станции Петушки к своей возлюбленной. Как только Венечка садится в поезд, он начинает избавляться от страшного недуга – похмелья, употребляя алкоголь на протяжении всей поездки. Венечке известно, что его возлюбленная отправилась к нему навстречу и ждёт его на одной из станций. Если с момента начала употребления напитков проходит t часов и Венечка не встречает свою возлюбленную ни на одной из пройденных им станций, то от грусти и количества выпитого он засыпает и просыпается на Курском вокзале, где всё начинается сначала.
Железная дорога, по которой едет поезд Венечки, соединена n станциями. Переход от станции u к станции v занимает w часов. Венечка не хочет каждый раз выходить на станции и искать возлюбленную, поэтому хочет знать наверняка – сможет ли он гарантированно найти её на одной из станций.
Первая строка входного файла содержит два целых числа n и m — количества станций и переходов между станциями соответственно. Далее идут m строк, в каждой из которых указаны три целых числа через пробел:
Вторая строка входного файла содержит одно целое число t - всего часов, данные Венечки для поиска возлюбленной.
Станция Курского вокзала в каждом примере имеет номер 0.
n ≤ 100,
0 ≤ m ≤ n2.
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|