Come and Go

Input

The input contains several test cases. The first line of a test case contains two integers $n$ (2 \le n \le 2000) and $m$ (2 \le m \le n \cdot (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 \le v, w \le n, v \neq 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.

Examples