Авіапроїздний#6305
Одна авіакомпанія проводить цікаву акцію. Вона продає проїзні, які діють за наступними правилами:
Кожному авіарейсу компанії присвоюється певна вартість в умовних одиницях.
Проїзний має певний номінал (у тих же умовних одиницях).
Після кожного перельоту з проїзного списується кількість умовних одиниць, рівна вартості цього перельоту.
Кожен наступний переліт повинен починатися у тому місті, у якому завершився попередній.
Якщо кількість умовних одиниць, що залишилась на проїзному, недостатня для здійснення наступного перельоту, то вони згорають.
Знаючи номінал проїзного та вартості усіх авіарейсів, потрібно визначити, чи можна скласти план перельотів так, щоб використати проїзний повністю, не втративши жодної умовної одиниці.
У першому рядку знаходяться три натуральних числа, відокремлених пропуском:
(1 \leq n \leq 1000) — кількість міст, у які літають рейси авіакомпанії, (1 \leq m \leq 1000) — кількість рейсів, (1 \leq v \leq 1000) — номінал проїзного.
У кожному з наступних рядків задано вартості перельотів. Перші два числа у рядку v_1 та v_2 (1 \leq v_1, v_2 \leq n, v_1 \neq v_2) — номери міст, з'єднаних авіарейсом, а третє (1 \leq w \leq 1000) — вартість перельоту з міста v_1 у місто v_2. Числа у рядку відокремлено пропуском.
Відомо, що будь-які два міста з'єднані напряму не більше, ніж одним авіарейсом у кожному з двох напрямків.
Вивести YES, якщо можливо скласти план перельотів, що дозволяє використати проїзний повністю, та NO у протилежному випадку.
Приклад 1