#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxN 10
#define MIN(a, b) ((a)<(b)?(a):(b))
#define MAX(a, b) ((a)>(b)?(a):(b))
int g[maxN][maxN], cur[maxN], pre[maxN], gap[maxN], dist[maxN];
int n, m, s, t, f;
int need[maxN];
bool flag;
int SAP(){
	int u, v, maxflow=0, aug=0xfffffff;
	memset(gap, 0, sizeof(gap));
	memset(dist, 0, sizeof(dist));
	for(int i=0; i<=n; i++) cur[i]=1;
	u=pre[s]=s; gap[0]=n;
	while(dist[s]<n){
		loop:
		for(v=cur[u]; v<=n; v++) if(g[u][v]>0 && dist[u]==dist[v]+1){
			aug=MIN(aug, g[u][v]);
			pre[v]=u; cur[u]=v; u=v;
			if(v==t){
				maxflow+=aug;
				for(u=pre[u]; v!=s; v=u, u=pre[u]){
					g[u][v]-=aug;
					g[v][u]+=aug;
				}
				aug=0xfffffff;
			}
			goto loop;
		}
		int mind=n;
		for(v=1; v<=n; v++) if(g[u][v]>0 && mind>dist[v]){
			cur[u]=v;
			mind=dist[v];
		}
		if((--gap[dist[u]])<=0) break;
		gap[dist[u]=mind+1]++;
	}
	return maxflow;
}
int main(){
	int tc, a, b, c;
	scanf("%d", &tc);
	while(tc--){
		scanf("%d %d", &n, &m);
		memset(g, 0, sizeof(g));
		memset(need, 0, sizeof(need));
		for(int i=0; i<m; i++){
			scanf("%d %d %d", &a, &b, &c);
			if(a==b) continue;
			need[a]++; need[b]--;
			if(c!=1){
				g[b][a]++;
			}
		}
		flag=true; f=0;
		for(int i=1; i<=n; i++){
			if(need[i]%2==0){
				need[i]/=2;
				if(need[i]>0) {g[i][n+2]=need[i];f+=need[i];}
				else g[n+1][i]=-need[i];
			}
			else flag=false;
		}
		s=n+1; t=n+2;
		n+=2;
		if(!flag || SAP()!=f) printf("impossible\n");
		else printf("possible\n");
	}
	return 0;
}