In a certain city there are 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 v and w it must be possible to travel from v to w and from w to 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.

Input

The input contains several test cases. The first line of a test case contains two integers n (2 ≤ n ≤ 2000) and m (2 ≤ m ≤ n * (n − 1) / 2), separated by a space, indicating the number of intersections and number of streets. The next m lines describe the city street system, with each line describing one street. A street description consists of three integers v, w (1 ≤ v, w ≤ n, v ≠ w) and p, separated by a blank space, where v and w are distinct identifiers for intersections and p can be 1 or 2. If p = 1 the street is one-way, and traffic goes from v to w, if p = 2 then the street is two-way and links v and 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.

Output

For each test case your program should print a single line containing an integer g, where g is equal to one if the condition of connectedness is satisfied, and g is zero otherwise.