Прийди і піди
У певному місті є 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 дорівнює нулю в протилежному випадку.