Come and Go

A city has $N$ intersections joined by one-way streets and two-way streets. Many of the streets run through tunnels or over viaducts.

The road network must allow a round trip between any two intersections: for any intersections $V$ and $W$, it must be possible to travel from $V$ to $W$ and from $W$ to $V$.

Read the description of a city's road network and decide whether that requirement holds.

The input contains several test cases. The first line of a test case has two integers $N$ and $M$ separated by a single space, the number of intersections and the number of streets ($2 \le N \le 2000$, $2 \le M \le N(N-1)/2$). Each of the next $M$ lines describes one street with three integers $V$, $W$ and $P$, separated by single spaces. $V$ and $W$ are distinct intersection numbers ($1 \le V, W \le N$, $V \ne W$), and $P$ is 1 or 2. If $P$ is 1, the street is one-way and runs from $V$ to $W$. If $P$ is 2, the street connects $V$ and $W$ in both directions. No two streets connect the same pair of intersections.

The last test case is followed by a line containing two zeros separated by a single space. Do not process that line.

For each test case, print one line with an integer $G$. $G$ is 1 if the connectivity requirement holds, and 0 otherwise.