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