#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int maxN=205,inf=0x3f3f3f3f;
int cap[maxN][maxN],pre[maxN],flow[maxN],m,s,in[maxN],out[maxN],sum;

bool build()
{
	sum=0;
	memset(cap,0,sizeof(cap));
	memset(in,0,sizeof(in));
	memset(out,0,sizeof(out));
	scanf("%d%d",&m,&s);
	while (s--)
	{
		int i,j,k;
		scanf("%d%d%d",&i,&j,&k);
		if (!k) cap[i][j]++;
		in[j]++,out[i]++;
	}
	for (int i = 1; i <= m; i++)	
	{
		if ((in[i]-out[i])&1)
			return false;	
		if (out[i]>in[i]) sum+=(cap[0][i]=((out[i]-in[i])>>1));		
		else if (in[i]>out[i]) cap[i][m+1]=((in[i]-out[i])>>1);				
	}
	return true;
}

int bfs(int src,int des)
{
	memset(pre,-1,sizeof(pre));
	pre[src]=-2;
	flow[src]=inf;
	queue<int> q;
	q.push(src);
	while (!q.empty())
	{
		int front=q.front();
		q.pop();
		if (front==des) return flow[des];
		for (int i = 0; i <= m+1; i++)
		{
			if (!~pre[i]&&cap[front][i]>0)
			{
				flow[i]=min(flow[front],cap[front][i]);
				pre[i]=front;
				q.push(i);
			}
		}
	}
	return -1;
}

int ek(int src,int des)
{
	int ret=0,k,d,x;
	while (~(d=bfs(src,des)))
	{
		k=des;
		while (k!=src)
		{
			x=pre[k];
			cap[x][k]-=d;
			cap[k][x]+=d;
			k=x;
		}
		ret+=d;
	}
	return ret;
}

int main()
{
//	freopen("D:\\input.txt","r",stdin);
	int kase;
	scanf("%d",&kase);
	while (kase--)
	{		
		if (!build())
		{
			puts("impossible");
			continue;
		}
		if (ek(0,m+1)==sum) puts("possible");
		else puts("impossible");
	}
	return 0;
}