Description

Original source: USACO 2006 Dec. Gold, original problem can be found at POJ 3259

While wandering around his farm, John discovered several wormholes. A wormhole can be considered a very peculiar directed edge that can transport you back to a moment in the past (relative to the time before you entered the wormhole). Each of John's farms consists of $N$ fields (labeled from $1$ to $N$) connected by $M$ bidirectional paths (undirected edges) and $W$ wormholes.

Now John wants to use these wormholes to go back in time (return to the starting point before the departure time). Please tell him if this is possible. John will provide you with the maps of $F$ farms. No path will take you more than $10^4$ seconds to traverse, and no wormhole will take you back more than $10^4$ seconds.

Input Format

The first line contains an integer $F$, the number of farms;

For each farm:

The first line contains three integers $N, M, W$;

The next $M$ lines each contain three integers $S, E, T$, indicating a bidirectional path between field $S$ and field $E$ that takes $T$ seconds to traverse;

The next $W$ lines each contain three integers $S, E, T$, indicating a wormhole from field $S$ to field $E$ that transports John $T$ seconds into the past.

Output Format

Output $F$ lines in total. For the $i$-th farm, if John can achieve his goal, output YES on the $i$-th line; otherwise, output NO.

Sample 1

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

Data Range and Hints

For all data, $1\le F\le 5$, $1\le N\le 500$, $1\le M\le 2500$, $1\le W\le 200$, $1\le S,E\le N$, $|T|\le 10^4$.