2787: 「一本通 3.3 练习 2」虫洞
Memory Limit：512 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：28
Solved：7
Description
原题来自：USACO 2006 Dec. Gold，原文见 POJ 3259
John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John 的每个农场有 MMM 条小路（无向边）连接着 NNN（从 111 到 NNN 标号）块地，并有 WWW 个虫洞。
现在 John 想借助这些虫洞来回到过去（在出发时刻之前回到出发点），请你告诉他能办到吗。 John 将向你提供 FFF 个农场的地图。没有小路会耗费你超过 10410^4104 秒的时间，当然也没有虫洞回帮你回到超过 10410^4104 秒以前。
Input
第一行一个整数 FFF，表示农场个数；
对于每个农场：
第一行，三个整数 N,M,WN, M, WN,M,W；
接下来 MMM 行，每行三个数 S,E,TS, E, TS,E,T，表示在标号为 SSS 的地与标号为 EEE 的地中间有一条用时 TTT 秒的小路；
接下来 WWW 行，每行三个数 S,E,TS, E, TS,E,T，表示在标号为 SSS 的地与标号为 EEE 的地中间有一条可以使 John 到达 TTT 秒前的虫洞。
Output
输出共 FFF 行，如果 John 能在第 iii 个农场实现他的目标，就在第 iii 行输出 YES，否则输出 NO。
HINT
样例输入
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8样例输出
NO
YES对于全部数据，1≤F≤5,1≤N≤500,1≤M≤2500,1≤W≤200,1≤S,E≤N,∣T∣≤1041le Fle 5,1le Nle 500,1le Mle 2500,1le Wle 200,1le S,Ele N,|T|le 10^41≤F≤5,1≤N≤500,1≤M≤2500,1≤W≤200,1≤S,E≤N,∣T∣≤104。