bellman-ford:

/*
 * Author: kymo
 * Created Time:  2011/7/23 15:49:21
 * File Name: bellman-ford.cpp
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
#define F(a,b) for(int i = a;i <= b;i ++)
#define int_max 99999999999LL
#define eps 1.0e-6
#define max 5240
#define inf 100000
int d[max];
int edge;
struct node{
    int u,v;
    int val;
}Node[max];
int n,e,m;
bool bellman_ford(int s){
    for(int j = 0;j <= n-1;j ++){
       d[j] = inf;
    }
    d[s] = 0;
    int flag = 0;
    for(int t = 0;t <= n-2;t ++){
        for(int j = 0;j <= edge-1;j ++){
            if(d[Node[j].u] != inf&&d[Node[j].u] + Node[j].val < d[Node[j].v]){
                d[Node[j].v] = d[Node[j].u] + Node[j].val;
            }
        }
    }
    for(int j = 0;j <= edge-1;j ++){
        if(d[Node[j].u] + Node[j].val < d[Node[j].v]){
            flag = 1;
            break;
        }
    }
    if(flag) return false;
    else return true;
}
int T;
int a,b,c;
int main() {
    cin>>T;
    for(int i = 0;i <= T-1;i ++){
        scanf("%d%d%d",&n,&e,&m);
        edge = 0;
        for(int j = 0;j <= e-1;j ++){
            scanf("%d%d%d",&a,&b,&c);
            Node[edge].u = a-1;
            Node[edge].v = b-1;
            Node[edge].val = c;
            edge ++;
            Node[edge].u = b-1;
            Node[edge].v = a-1;
            Node[edge].val = c;
            edge ++; 
        }
        for(int j = 0;j <= m-1;j ++){
            scanf("%d%d%d",&a,&b,&c);
            Node[edge].u = a-1;
            Node[edge].v = b-1;
            Node[edge].val = -1*c;
            edge ++;
        }
        if(bellman_ford(0)) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

spfa:

/*
 * Author: kymo
 * Created Time:  2011/7/24 10:04:02
 * File Name: 3259-spfa.cpp
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string.h>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#define F(a,b) for(int i = a;i <= b;i ++)
#define int_max 99999999999LL
#define eps 1.0e-6
#define inf 99999999
#define max 520
int n,m,w;
int a,b,c;
int d[max];
int cnt[max];
int vis[max];
struct node{
    int v;
    int val;
}E;
vector<node> Node[max+2];
int spfa(int k){
    for(int j = 1;j <= n;j ++){
        d[j] = inf;
        cnt[j] = 0;
        vis[j] = 0;
    }
    d[k] = 0;
    vis[k] = 1;
    cnt[k] = 1;
   queue<int> some;
   some.push(k);
   while(!some.empty()){
        int tp = some.front();
        some.pop();
        int size = Node[tp].size();
        vis[tp] = 0;
        for(int j = 0;j <= size-1;j ++){
            E = Node[tp][j];
            if(d[E.v] - E.val > d[tp]){
                d[E.v] = E.val + d[tp];
                if(!vis[E.v]){
                    vis[E.v] = 1;
                    cnt[E.v] ++;
                    if(cnt[E.v] >= n) return 0;
                    some.push(E.v);
                }
            }       
        }
    }
    return 1;
}
int main() {
    int T;
    scanf("%d",&T);
    for(int TT = 0;TT <= T-1;TT ++){
        scanf("%d%d%d",&n,&m,&w);
        for(int j = 1;j <= n;j ++){
            Node[j].clear();
        }
        for(int j = 0;j <= m-1;j ++){
            scanf("%d%d%d",&a,&b,&c);
            E.v = b;
            E.val = c;
            Node[a].push_back(E);
            E.v = a;
            E.val = c;
            Node[b].push_back(E);
        }
        
        for(int j = 0;j <= w-1;j ++){
            scanf("%d%d%d",&a,&b,&c);
            E.v = b;
            E.val = -c;
            Node[a].push_back(E);
        }
        int ret = 0;
        if(spfa(1)) ret = 1;
        if(!ret) printf("YES\n");
        else printf("NO\n"); 
    } 
    return 0;
}