belmenford

#include <bits/stdc++.h>

using namespace std;


vector < int > v [2010];
vector < int > cost [2010];
int d [ 2010 ] ;
const int infinity = 1e9;
int n , m ;
int bellman ( int src ) {
d [ src ] = 0 ;
for ( int i = 0 ; i < n  ; i ++)d[i]=infinity;
for ( int i = 0 ; i < n - 1 ; i ++ ) { // n = vertex number

    for ( int u = 0 ; u < n ; u ++ ) { // for every edge (u-v)

       for ( int k = 0 ; k < v [ u ].size() ; k ++ ) {
          if ( d [ u ] + cost [ u ][ k ] <  d [ v [ u] [ k ] ] ){
                 d [ v [ u] [ k ] ] = d [ u ] + cost [ u ][k]  ;

          }


       }

    }

}
}

bool cycle ( ){

    for ( int u = 0 ; u < n ; u ++ ) {

       for ( int k = 0 ; k < v [ u ].size() ; k ++ ) {
          if ( d [ u ] + cost [ u ][ k ] <  d [ v [ u] [ k ] ] ){
                return true ;

          }


       }

    }
    return false ;







}
int main()
{

    int t ;
    cin >> t ;
    while(t--){
    cin >>  n >> m;
    for ( int i = 0 ; i < m ;  i ++ ){
        int a , b , c ;
        cin >> a >> b >> c;
        v[a].push_back(b);
        cost[a].push_back(c);
    }
    bellman(0);
    bool bp = cycle();
    if ( bp ){
        cout <<"possible"<<endl;
    }else cout <<"not possible"<<endl;
    for ( int i = 0 ; i < n ; i ++)v[i].clear();
    for ( int i = 0 ; i  < n ; i ++ )cost[i].clear();
    }

    return 0;
}