В некотором городе имеется \textbf{N} перекрестков, соединенных между собою одно- или двусторонними дорогами. Это современный город, некоторые улицы имеют тоннели и эстакады. Очевидно, что должна существовать возможность прохода между любыми двумя перекрестками. То есть для любых двух перекрестков \textbf{V} и \textbf{W} должен существовать путь из \textbf{V} в \textbf{W} и из \textbf{W} в \textbf{V}. Ваша программа должна прочитать систему улиц города и определить, имеет ли в ней место указанное требование связности. \InputFile Входные данные состоят из нескольких тестов. Первая строка теста содержит количество перекрестков \textbf{N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{2000}) и количество улиц \textbf{M} (\textbf{2} ≤ \textbf{M} ≤ \textbf{N(N - 1)/2}). Следующие \textbf{M }строк описывают систему улиц города, одна строка задает одну улицу. Описание улицы состоит из трех чисел \textbf{V}, \textbf{W} и \textbf{P}, где \textbf{V} и \textbf{W} - различные номера перекрестков (\textbf{1} ≤ \textbf{V}, \textbf{W }≤ \textbf{N}, \textbf{V} ≠ \textbf{W}), а \textbf{P} равно \textbf{1} или \textbf{2}; если \textbf{P = 1}, то улица однонаправленная, и движение происходит в направлении от \textbf{V} к \textbf{W}; если \textbf{P = 2}, то улица двунаправленная, связывающая \textbf{V} и \textbf{W}. Каждая пара перекрестков соединена максимум одной улицей. Последняя строка содержит два нуля и не обрабатывается. \OutputFile Для каждого теста вывести в отдельной строке единицу, если условие связности имеет место, и ноль в противоположном случае.