eolymp
bolt
Try our new interface for solving problems
Problems

Авиапроездной

Авиапроездной

Time limit 1 second
Memory limit 64 MiB

Одна авиакомпания проводит интересную акцию. Она продает проездные, которые действуют по следующим правилам:

  • каждому авиарейсу компании присваивается некоторая стоимость в условных единицах

  • проездной имеет определенный номинал (в тех же условных единицах);

  • после каждого перелета с проездного списывается количество условных единиц, равное стоимости этого перелета;

  • каждый следующий перелет должен начинаться в том городе, в котором закончился предыдущий;

  • если оставшееся на проездном количество условных единиц недостаточно для совершения следующего перелета, то они сгорают.

Зная номинал проездного и стоимости всех авиарейсов, требуется определить, можно ли составить план перелетов так, чтобы использовать проездной полностью, не потеряв ни одной условной единицы.

Input data

В первой строке находятся три натуральных числа, разделенных пробелом:

n (1n1000) – количество городов, в которые летают рейсы авиакомпании,

m (1m1000) – количество рейсов,

v – номинал проездного (1v1000).

В каждой из следующих m строк заданы стоимости перелетов. Первые два числа в строке v_1 и v_2 (1v_1, v_2n) – номера городов, связанных авиарейсом, а третье w (1w1000) – стоимость перелета из города v_1 в город v_2 (v_1 и v_2 различны). Числа в строке разделены пробелом.

Известно, что любые два города связаны напрямую не более чем одним авиарейсом в каждом из двух направлений.

Output data

Вывести YES, если возможно составить план перелетов, позволяющий использовать проездной полностью, и NO в противном случае.

Examples

Input example #1
4 5 8
1 2 2
1 3 3
3 4 2
3 2 2
2 1 2
Output example #1
YES
Source Новосибирск 2013