In a certain city there are \textbf{N} intersections connected by one-way and two-way streets. It is a modern city, and several of the streets have tunnels or overpasses. Evidently it must be possible to travel between any two intersections. More precisely given two intersections \textbf{V} and \textbf{W} it must be possible to travel from \textbf{V} to \textbf{W} and from \textbf{W} to \textbf{V}. Your task is to write a program that reads a description of the city street system and determines whether the requirement of connectedness is satisfied or not. \InputFile The input contains several test cases. The first line of a test case contains two integers \textbf{N} and \textbf{M}, separated by a space, indicating the number of intersections (\textbf{2} ≤ \textbf{N} ≤ \textbf{2000}) and number of streets (\textbf{2} ≤ \textbf{M} ≤ \textbf{N(N - 1)/2}). The next \textbf{M }lines describe the city street system, with each line describing one street. A street description consists of three integers \textbf{V}, \textbf{W} and \textbf{P}, separated by a blank space, where \textbf{V} and \textbf{W} are distinct identifiers for intersections (\textbf{1} ≤ \textbf{V}, \textbf{W }≤ \textbf{N}, \textbf{V} ≠ \textbf{W}) and \textbf{P} can be \textbf{1} or \textbf{2}; if \textbf{P = 1} the street is one-way, and traffic goes from \textbf{V} to \textbf{W}; if \textbf{P = 2} then the street is two-way and links \textbf{V} and \textbf{W}. A pair of intersections is connected by at most one street. The last test case is followed by a line that contains only two zero numbers separated by a blank space. \OutputFile For each test case your program should print a single line containing an integer \textbf{G}, where \textbf{G} is equal to one if the condition of connectedness is satisfied, and \textbf{G} is zero otherwise.