558 - Wormholes

#include<cstdio>
#include<iostream>
#define SZ 2005
using namespace std;

int edge_u[SZ],edge_v[SZ],edge_cost[SZ],d[SZ];
int main()
{
    int test,n,m,update,u,v,step,neg_cycle,i;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            d[i]=100000;
        }
        d[1]=0;
        for(i=1;i<=m;i++)
        {
            cin>>edge_u[i]>>edge_v[i]>>edge_cost[i];
        }
        neg_cycle=0;
        for(step=1;step<=n;step++)
        {
            update=0;
            for(i=1;i<=m;i++)
            {
                u=edge_u[i];
                v=edge_v[i];
                if(d[u]+edge_cost[i]<d[v])
                {
                    update=1;
                    if(step==n)
                    {
                        neg_cycle=1;
                    }
                    d[v]=d[u]+edge_cost[i];
                }
            }
            if(update==0)
            {
                break;
            }
        }
        if(!neg_cycle)
        {
            printf("not possible\n");
        }
        else
        {
            printf("possible\n");
        }
    }
    return 0;
}