Авіапроїздний
Одна авіакомпанія проводить цікаву акцію. Вона продає проїздні, які діють за наступними правилами:
кожному авіарейсу компанії присвоюється деяка віртість в умовних одиницях
проїздний має певний номвнал (у тих же умовних одиницях);
після кожного перельоту з проїздного списується кількість умовних одиниць, рівна вартості цього перельоту;
кожен наступний переліт повинен починатись у тому місті, у якому завершився попередній;
якщо кількість умовних одиниць, що залишилась на проїздному, недостатня для здійснення наступного перельоту, то вони згорають.
Знаючи номінал проїздного та вартості усіх авіарейсів, потрібно визначити, чи можно скласти план перельотів так, щоб використати проїздний повністю, не втративши жодної умовної одиниці.
Вхідні дані
У першому рядку знаходяться три натуральних числа, відокремлених пропуском:
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 у протилежному випадку.