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