#include <bits/stdc++.h>

#define pii pair<int,int>

using namespace std;

bool bellman_ford(int node, int edge, vector<pair<pii, int> > &adj)
{
    vector<long long int> dis(node, INT_MAX);
    dis[0]=0;

    for(int i=0; i<node; i++)
    {
        for(int j=0; j<edge; j++)
        {
            int u=adj[j].first.first;
            int v=adj[j].first.second;
            int cost=adj[j].second;
            if(dis[u] != INT_MAX && dis[v] > dis[u]+cost)
            {
                dis[v]=dis[u]+cost;
            }
        }
    }
    //Running an extra loop to find out whether the graph contains any negative cycle loop or not
    bool neg_cycle=0;
    for(int j=0; j<edge; j++)
    {
        int u=adj[j].first.first;
        int v=adj[j].first.second;
        int cost=adj[j].second;
        if(dis[u] != INT_MAX && dis[v] > dis[u]+cost)
        {
            neg_cycle=1;
            break;
            //dis[v]=INT_MAX; //Marking the nodes which will keep decreasing infinitly due to negative weight cycle
        }
    }
    return neg_cycle;
}


int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int t;
    cin>>t;
    while(t--)
    {
        int node,edge;
        cin>>node>>edge;

        vector<pair<pii, int> > adj;


        for(int i=0; i<edge; i++)
        {
            int from,to,w;
            cin>>from>>to>>w;
            adj.push_back({{from, to}, w});
        }
        if(bellman_ford(node, edge, adj)) cout<<"possible"<<endl;
        else cout<<"not possible"<<endl;
    }
    return 0;
}