Sightseeing Tour

The city council wants to run a sightseeing bus tour through the city so that tourists can see every corner of it. The tour must be planned so that every street is driven along exactly once, and the bus must start and finish at the same junction. Streets are either one-way or two-way, and the tour bus must obey these traffic rules. Determine whether such a sightseeing tour can be constructed.

The first line contains a single positive integer $n$, the number of test scenarios.

Each scenario begins with a line containing two positive integers $m$ and $s$ ($1 \le m \le 200$, $1 \le s \le 1000$): the number of junctions and the number of streets.

Each of the next $s$ lines describes one street with three integers $x_i$, $y_i$, and $d_i$ ($1 \le x_i, y_i \le m$, $0 \le d_i \le 1$), where $x_i$ and $y_i$ are the junctions joined by the street. If $d_i = 1$ the street is one-way (from $x_i$ to $y_i$); otherwise it is two-way. You may assume there is a junction from which every other junction can be reached.

For each scenario, output a single line containing possible if a sightseeing tour can be constructed, or impossible otherwise.