Background

NO BACKGROND

Description

原题来自：USACO 2006 Dec. Gold，原文见 POJ 3259

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John 的每个农场有 MMM 条小路（无向边）连接着 NNN（从 111 到 NNN 标号）块地，并有 WWW 个虫洞。

现在 John 想借助这些虫洞来回到过去（在出发时刻之前回到出发点），请你告诉他能办到吗。 John 将向你提供 FFF 个农场的地图。没有小路会耗费你超过 10410^410
​4
​​ 秒的时间，当然也没有虫洞回帮你回到超过 10410^410
​4
​​ 秒以前。

Format

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。

Sample 1

Input

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

Output

NO
YES

Limitation

1s, 1024KiB for each test case.

Source

对于全部数据，1≤F≤5,1≤N≤500,1≤M≤2500,1≤W≤200,1≤S,E≤N,∣T|<=10^4