A zergling is sent on a dangerous journey - as part of a 4-pool build, the zergling has to run to the Protoss base to harass the mining probes.
On the way to the Protoss base, the zergling encounters some wormholes that teleport the zergling to a different space and time. The zergling comes up with an ingenious idea - if she can return to the Zerg main before she was born, then she could attack the Protoss base whenever she wanted to!
Note that beforehand, the zergling can decide which vertex to build the Zerg main at.
~1 \le T \le 5~
~1 \le N \le 500~
~1 \le M \le 2500~
~1 \le W \le 200~
~1 \le A_i, B_i \le N~
~1 \le T_i \le 10^4~
The first line will contain an integer ~T~, the number of test cases. ~T~ test cases follow.
Each test case starts with three space-separated integers, ~N~, ~M~, and ~W~.
Each of the next ~M~ lines contains three space-separated integers, ~A_i~, ~B_i~, and ~T_i~, indicating that there is a bidirectional path connecting vertices ~A_i~ and ~B_i~ that take ~T_i~ seconds to traverse.
Each of the next ~W~ lines contains three space-separated integers, ~A_i~, ~B_i~, and ~T_i~, indicating that there is a one-way wormhole connecting vertices ~A_i~ to ~B_i~ that takes the zergling back ~T_i~ seconds in the past.
For each test case, output
YES if it is possible for the zergling to travel back to the Zerg main before
she was born. Output
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