Time-Travel Cycle Detection

John has a farm of n fields numbered from 1 to n. The fields are connected by m bidirectional roads and w wormholes. Each road is a two‐way path which takes a certain amount of time to traverse, while each wormhole is a directed edge that takes you back in time (i.e. it subtracts time).

John wonders if there exists a cycle starting and ending at some field such that the total travel time is negative (meaning he ends up at a time earlier than he started). In other words, is there any cycle in the graph whose total weight is less than 0?

You are given the description of the farm: the fields, the roads (with positive travel times), and the wormholes (with the given time reduction). Determine whether such a time‐travel cycle exists.

Note: A road between u and v with a travel time t should be considered as two directed edges (u → v and v → u) with weight t, while a wormhole from u to v with time value t is a single directed edge with weight −t.

inputFormat

The first line of input contains an integer T (T ≥ 1) indicating the number of test cases.
For each test case, the first line contains three integers n, m, and w where:

• n (1 ≤ n ≤ 500) is the number of fields.
• m (1 ≤ m ≤ 2500) is the number of bidirectional roads.
• w (1 ≤ w ≤ 200) is the number of wormholes.

Then follow m lines, each containing three integers u, v, and t, which describe a road connecting field u and field v with travel time t (t > 0).

Then follow w lines, each containing three integers u, v, and t, which describe a wormhole from field u to field v that takes you back in time by t (t > 0).

outputFormat

For each test case, output a single line containing "YES" if a cycle exists that allows John to end up in a time earlier than his start time, otherwise output "NO".

sample

3
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
4 4 1
1 2 3
2 3 4
3 4 8
4 1 10
3 1 15
2 1 1
1 2 3
2 1 4

NO
YES
YES