558

#include <iostream>
#include <cstdio>
#include <cstdlib>

#define INF 1000000000
#define MX 2005

using namespace std;

struct Edge{
	int src;
	int dst;
	int weight;
	};

Edge e[MX];

bool bellman(int n,int m,int source)
{
	bool negativecycle =false;
	int dist[n+5];
	dist = 0;

	for(int i=1;i<n;i++)
		dist[i]=INF;

	for(int i=1;i<=n-1;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(dist[e[j].dst]>dist[e[j].src]+e[j].weight)
				dist[e[j].dst] = dist[e[j].src]+e[j].weight;
		}
	}


	for(int j=0;j<m;j++)
	{
		if(dist[e[j].dst]>dist[e[j].src]+e[j].weight)
			negativecycle = 1;
	}

	return negativecycle;
}


int main()
{
	int n,m,t;
	int s,d,tym;

	cin>>t;

	while(t--)
	{
		cin>>n>>m;
		for(int i=0;i<m;i++)
		{
			cin>>s>>d>>tym;
			e[i].src = s;
			e[i].dst = d;
			e[i].weight = tym;
		}
		if(bellman(n,m,0))
		cout<<"possible\n";
		else
		cout<<"not possible\n";
	}

	return 0;
}