00558 - Wormholes

#include <stdio.h>
#include <string.h>

int main()
{
    int cases;
    scanf("%d", &cases);

    for(int n, m; cases-- && scanf("%d%d", &n, &m);)
    {
        int dist[n], u[m], v[m], w[m], ok=0;
        memset(dist, 127, sizeof(dist));
        dist[0]=0;

        for(int i=0; i<m; i++)
            scanf("%d%d%d", u+i, v+i, w+i);

        for(int i=1, use=1; i<n && use; i++)
            for(int j=use=0; j<m; j++)
                if(dist[v[j]]>dist[u[j]]+w[j] && dist[u[j]]!=0x7f7f7f7f)
                    dist[v[j]]=dist[u[j]]+w[j], use=1;

        for(int i=0; i<m && !ok; i++)
            if(dist[v[i]]>dist[u[i]]+w[i] && dist[u[i]]!=0x7f7f7f7f)
                ok=1;

        puts(ok?"possible":"not possible");
    }
}