관광 버스 투어

시에서 관광객이 도시의 구석구석을 볼 수 있도록 버스로 관광 투어를 운행하려고 한다. 투어는 도시의 모든 도로를 정확히 한 번씩 지나도록 계획해야 하며, 버스는 같은 교차로에서 출발해 같은 교차로로 돌아와야 한다. 도로는 일방통행이거나 양방향 통행이며, 투어 버스는 이 교통 규칙을 지켜야 한다. 이러한 조건을 만족하는 관광 투어를 만들 수 있는지 판별하여라.

첫째 줄에 시나리오의 수를 나타내는 양의 정수 $n$이 주어진다.

각 시나리오의 첫째 줄에는 교차로의 수 $m$과 도로의 수 $s$가 주어진다 ($1 \le m \le 200$, $1 \le s \le 1000$).

이어지는 $s$개의 줄에는 각 도로가 세 정수 $x_i$, $y_i$, $d_i$로 주어진다 ($1 \le x_i, y_i \le m$, $0 \le d_i \le 1$). $x_i$와 $y_i$는 그 도로가 잇는 두 교차로이다. $d_i = 1$이면 그 도로는 $x_i$에서 $y_i$로 향하는 일방통행 도로이고, $d_i = 0$이면 양방향 도로이다. 어떤 한 교차로에서 다른 모든 교차로에 도달할 수 있다고 가정해도 좋다.

각 시나리오마다 관광 투어를 만들 수 있으면 possible을, 그렇지 않으면 impossible을 한 줄에 출력한다.