Одна авиакомпания проводит интересную акцию. Она продает проездные, которые действуют по следующим правилам: \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} в противном случае.