ACM Новосибирск 2013
Авиапроездной
Одна авиакомпания проводит интересную акцию. Она продает проездные, которые действуют по следующим правилам:
каждому авиарейсу компании присваивается некоторая стоимость в условных единицах
проездной имеет определенный номинал (в тех же условных единицах);
после каждого перелета с проездного списывается количество условных единиц, равное стоимости этого перелета;
каждый следующий перелет должен начинаться в том городе, в котором закончился предыдущий;
если оставшееся на проездном количество условных единиц недостаточно для совершения следующего перелета, то они сгорают.
Зная номинал проездного и стоимости всех авиарейсов, требуется определить, можно ли составить план перелетов так, чтобы использовать проездной полностью, не потеряв ни одной условной единицы.
Input data
В первой строке находятся три натуральных числа, разделенных пробелом:
n (1 ≤ n ≤ 1000) – количество городов, в которые летают рейсы авиакомпании,
m (1 ≤ m ≤ 1000) – количество рейсов,
v – номинал проездного (1 ≤ v ≤ 1000).
В каждой из следующих m строк заданы стоимости перелетов. Первые два числа в строке v1 и v2 (1 ≤ v1, v2≤ n) – номера городов, связанных авиарейсом, а третье w (1 ≤ w ≤ 1000) – стоимость перелета из города v1 в город v2 (v1 и v2 различны). Числа в строке разделены пробелом.
Известно, что любые два города связаны напрямую не более чем одним авиарейсом в каждом из двух направлений.
Output data
Вывести YES, если возможно составить план перелетов, позволяющий использовать проездной полностью, и NO в противном случае.
Examples
4 5 8 1 2 2 1 3 3 3 4 2 3 2 2 2 1 2
YES