(UVa) 558 – Wormholes

/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=499
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf

using namespace std;

#define MAXX 2002

struct DATA{
    int p, q, w;
};


int stars, countPaths;
DATA paths[MAXX];
ll dist[MAXX];

bool bellmanFord()
{
    loop(i, stars)
    {
        dist[i] = INF;
    }

    dist[1] = 0;

    loop(i, stars-1)
    {
        loop(j, countPaths)
        {
            if( dist[ paths[j].p ] + paths[j].w < dist[ paths[j].q ]  )
            {
                dist[ paths[j].q ] = dist[ paths[j].p ] + paths[j].w;
            }
        }
    }

    loop(j, countPaths)
    {
        if( dist[ paths[j].p ] + paths[j].w < dist[ paths[j].q ]  )
        {
            return false;
        }
    }
    return true;
}








int main()
{
    int kases;
    getint(kases);
    int p, q, w;
    while(kases--)
    {
        getint(stars); getint(countPaths);
        loop(i, countPaths)
        {
            getint(paths[i].p); getint(paths[i].q); getint(paths[i].w);
        }

        if(!bellmanFord())
        {
            pf("possible\n");
        }
        else
        {
            pf("not possible\n");
        }


    }

    return 0;
}