[USACO06DEC] Wormholes G

题目背景

[英文题面见此链接](https://www.luogu.com.cn/paste/mxuf6zpl)

题目描述

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边,并可以使你返回到过去的一个时刻(相对你进入虫洞之前)。 John 的每个农场有 $m$ 条小路(无向边)连接着 $n$ 块地(从 $1 \sim n$ 标号),并有 $w$ 个虫洞。 现在 John 希望能够从某块地出发,走过一条路径回到出发点,且同时也回到了出发时刻以前的某一时刻。请你告诉他能否做到。

输入输出格式

输入格式


输入的第一行是一个整数 $T$,代表测试数据的组数。 每组测试数据的格式如下: 每组数据的第一行是三个用空格隔开的整数,分别代表农田的个数 $n$,小路的条数 $m$,以及虫洞的个数 $w$。 每组数据的第 $2$ 到第 $(m + 1)$ 行,每行有三个用空格隔开的整数 $u, v, p$,代表有一条连接 $u$ 与 $v$ 的小路,经过这条路需要花费 $p$ 的时间。 每组数据的第 $(m + 2)$ 到第 $(m + w + 1)$ 行,每行三个用空格隔开的整数 $u, v, p$,代表点 $u$ 存在一个虫洞,经过这个虫洞会到达点 $v$,并回到 $p$ 秒之前。

输出格式


对于每组测试数据,输出一行一个字符串,如果能回到出发时刻之前,则输出 `YES`,否则输出 `NO`。

输入输出样例

输入样例 #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

输出样例 #1

NO
YES

说明

#### 样例 2 解释 John 只需要沿着 $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ 的路径一直转圈即可,每转完一圈,时间就会减少一秒。 #### 数据范围与约定 对于 $100\%$ 的数据,$1 \le T \le 5$,$1 \le n \le 500$,$1 \le m \le 2500$,$1 \le w \le 200$,$1 \le p \le 10^4$。