大意：虫洞旅行，前面一部分（n组）是双向正权，后面一部分（w组）是单向负权，判断有没有负权环。
思路：由于有负权边，就不能Dijkstra了，用Bellman_Ford。就是看图中有没有负权环，有的话可以无限次走这个环，使得时间一定能得到一个负值。所以有的存在负环话就是可以，没有的话就是不可以了。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max = 10001
struct node
{
int s, e, t;
} q[5010];
int dis[520];
bool Bellman_Ford(int n, int r)
{
memset(dis, 0, sizeof(dis));
for(int i = 1; i <= n; i++)
{
bool flag = false;
for(int j = 1; j <= r; j++)
{
if(dis[q[j].e] > dis[q[j].s]+q[j].t)
{
dis[q[j].e] = dis[q[j].s]+q[j].t;
flag = true;
}
}
if(!flag)
{
break;
}
}
for(int i = 1; i <= r; i++)
{
if(dis[q[i].e] > dis[q[i].s]+q[i].t)
{
return true;
}
}
return false;
}
void Solve()
{
int p, n, m, w, a, b, c;
scanf("%d", &p);
while(p--)
{
scanf("%d%d%d", &n, &m, &w);
int r = 0;
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &a, &b, &c);
q[++r].s = a;
q[r].e = b;
q[r].t = c;
q[++r].s = b;
q[r].e = a;
q[r].t = c;
}
for(int i = 1; i <= w; i++)
{
scanf("%d%d%d", &a, &b, &c);
q[++r].s = a;
q[r].e = b;
q[r].t = -c;
}
if(Bellman_Ford(n, r))
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
}
int main()
{
Solve();
return 0;
}