Авиапроездной
Одна авиакомпания проводит интересную акцию. Она продает проездные, которые действуют по следующим правилам:
каждому авиарейсу компании присваивается некоторая стоимость в условных единицах
проездной имеет определенный номинал (в тех же условных единицах);
после каждого перелета с проездного списывается количество условных единиц, равное стоимости этого перелета;
каждый следующий перелет должен начинаться в том городе, в котором закончился предыдущий;
если оставшееся на проездном количество условных единиц недостаточно для совершения следующего перелета, то они сгорают.
Зная номинал проездного и стоимости всех авиарейсов, требуется определить, можно ли составить план перелетов так, чтобы использовать проездной полностью, не потеряв ни одной условной единицы.
Входные данные
В первой строке находятся три натуральных числа, разделенных пробелом:
n (1 ≤ n ≤ 1000) – количество городов, в которые летают рейсы авиакомпании,
m (1 ≤ m ≤ 1000) – количество рейсов,
v – номинал проездного (1 ≤ v ≤ 1000).
В каждой из следующих m строк заданы стоимости перелетов. Первые два числа в строке v_1 и v_2 (1 ≤ v_1, v_{2 }≤ n) – номера городов, связанных авиарейсом, а третье w (1 ≤ w ≤ 1000) – стоимость перелета из города v_1 в город v_2 (v_1 и v_2 различны). Числа в строке разделены пробелом.
Известно, что любые два города связаны напрямую не более чем одним авиарейсом в каждом из двух направлений.
Выходные данные
Вывести YES, если возможно составить план перелетов, позволяющий использовать проездной полностью, и NO в противном случае.