В некотором городе имеется n перекрестков, соединенных улицами с односторонним и двусторонним движением. Это современный город, и на некоторых улицах имеются туннели или путепроводы. Очевидно, между любыми двумя перекрестками должна быть возможность перемещаться. Точнее, для любых двух пересечений v и w должна быть возможность проезда от v к w и от w к v.

Напишите программу, которая прочитает описание системы городских улиц и определит, выполняется ли требование связности.

Входные данные

Входные данные содержат несколько тестов. Первая строка каждого теста содержит два целых числа n (2 ≤ n ≤ 2000) и m (2 ≤ m ≤ n * (n − 1) / 2) - количество перекрестков и улиц. Следующие m строк описывают систему городских улиц, каждая строка описывает одну улицу. Описание улицы состоит из трех целых чисел v, w (1 ≤ v, w ≤ n, v ≠ w) и p, где v и w - разные номера перекрестков, p может быть 1 или 2. Если p = 1, то это улица с односторонним движением от v до w, если p = 2, то улица является двусторонней и связывает v и w. Пару перекрестков соединяет не более одной улицы.

Последняя строка содержит два нуля и не обрабатывается.

Выходные данные

Для каждого теста выведите единственную строку, содержащую целое число g, где g равно единице, если условие связности выполнено, и g равно нулю в противном случае.