UVa 558

//Bellman-ford
//UVa Q558
#include <bits/stdc++.h>
using namespace std;

struct edge{
    int u,v,w;
}e[2000];

int dist[1000];

int32_t main(){
    int n,m,t;
    cin >> t;
    while(t--){
        cin >> n >> m;
        dist[0] = 0;
        for(int i = 1; i < n; ++i)dist[i] = 1e9;
        for(int i = 0; i < m; ++i)cin >> e[i].u >> e[i].v >> e[i].w;
        for(int i = 0; i < n-1; ++i){
            for(int j = 0; j < m; ++j){
                dist[e[j].v] = min(dist[e[j].v], dist[e[j].u] + e[j].w);
            }
        }
        bool possible = 0;
        for(int i = 0; i < m; ++i){
            if(dist[e[i].v] > dist[e[i].u]+e[i].w){
                possible = 1;
                break;
            }
        }
        if(possible)cout << "possible\n";
        else cout << "not possible\n";
    }
    return 0 ;
}