Одна авіакомпанія проводить цікаву акцію. Вона продає проїздні, які діють за наступними правилами: \begin{itemize} \item кожному авіарейсу компанії присвоюється деяка віртість в умовних одиницях \item проїздний має певний номвнал (у тих же умовних одиницях); \item після кожного перельоту з проїздного списується кількість умовних одиниць, рівна вартості цього перельоту; \item кожен наступний переліт повинен починатись у тому місті, у якому завершився попередній; \item якщо кількість умовних одиниць, що залишилась на проїздному, недостатня для здійснення наступного перельоту, то вони згорають. \end{itemize} Знаючи номінал проїздного та вартості усіх авіарейсів, потрібно визначити, чи можно скласти план перельотів так, щоб використати проїздний повністю, не втративши жодної умовної одиниці. \InputFile У першому рядку знаходяться три натуральних числа, відокремлених пропуском: \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{1000}) -- кількість міст, у які літають рейси авіакомпанії, \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{1000}) -- кількість рейсів, \textbf{v} -- номінал проїздного (\textbf{1} ≤ \textbf{v} ≤ \textbf{1000}). У кожному з наступних \textbf{m} рядків задано вартості перельотів. Перші два числа у рядку \textbf{v_1} та \textbf{v_2} (\textbf{1} ≤ \textbf{v_1}, \textbf{v_2} ≤ \textbf{n}), -- номери міст, зв'язаних авіарейсом, а третє \textbf{w} (\textbf{1} ≤ \textbf{w} ≤ \textbf{1000}), -- вартість перельоту з міста \textbf{v_1} у місто \textbf{v_2 }(\textbf{v_1} та \textbf{v_2} різні). Числа у рядку відокремлено пропуском. Відомо, что довільні два міста зв'язані напряму не більше ніж одним авіарейсом у кожному з двох напрямків. \OutputFile Вивести \textbf{YES}, якщо можливо скласти план перельотів, який дозволяє використати проїздний повністю, та \textbf{NO} у протилежному випадку.