题目描述

探险家小明在勘察地形时发现了一种奇特的通道——时空隧道。它是一种单向传送装置，通过它不仅能瞬间到达目的地，还能让时间倒流！小明每片探险区域包含 $N (1 \le N \le 500)$ 个编号为 $1 \sim N$ 的据点、$M (1 \le M \le 2500)$ 条双向道路和 $W (1 \le W \le 200)$ 条时空隧道。

作为狂热的时间旅行爱好者，小明希望实现：从某个据点出发，经过若干道路和时空隧道后，在出发之前的时间回到起点。这样他就能与过去的自己相遇了 :)

为了判断可行性，小明将提供 $F (1 \le F \le 5)$ 个区域的完整地图。所有道路通行耗时不超过 $10\,000$ 秒，时空隧道最多能将小明带回到 $10\,000$ 秒前。

输入格式

第 $1$ 行：一个整数 $F$，表示区域数。后续为 $F$ 个区域的数据。

每个区域：

• 第 $1$ 行：三个空格分隔的整数 $N$（据点数）、$M$（双向道路数）、$W$（时空隧道数）。
• 第 $2 \sim M+1$ 行：每行三个空格分隔的整数 $(S, E, T)$，表示 $S$ 和 $E$ 间有一条耗时 $T$ 秒的双向道路。两个据点间可能存在多条道路。
• 第 $M+2 \sim M+W+1$ 行：每行三个空格分隔的整数 $(S, E, T)$，表示一条从 $S$ 到 $E$ 的单向时空隧道，可将小明带回到 $T$ 秒前。

输出格式

输出 $F$ 行：对每个区域，若小明能实现时间回溯则输出 YES，否则输出 NO。

样例

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

提示

• 区域 $1$：小明无法实现时间回溯。

• 区域 $2$：小明可通过环 $1 \to 2 \to 3 \to 1$ 回到起点 $1$ 秒前（可从环上任意点出发实现）。