Прийти та піти
У деякому місті є 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. Кожна пара перехресть з'єднана максимум однією вулицею.
Останній рядок містить два нулі і не опрацьовується.
Вихідні дані
Для кожного тесту вивести у окремому рядку одиницю, якщо умова зв'язності має місце, і нуль у протилежному випадку.