웜홀

N개의 지점, M개의 양방향 도로, W개의 단방향 웜홀이 있다. 도로는 양방향이고 이동 시간이 양수다. 웜홀은 단방향이며 통과하면 시간이 지정된 양만큼 줄어든다(음수 가중치). 어떤 지점에서 출발해 같은 지점으로 돌아올 때 시간이 과거로 되돌아가는지, 즉 음수 사이클이 존재하는지 판별한다.

벨만-포드 알고리즘으로 음수 사이클을 판별한다.

입력

첫째 줄에 테스트 케이스 수 TC가 주어진다.

각 테스트 케이스의 첫째 줄에 지점 수 N, 도로 수 M, 웜홀 수 W가 주어진다.

다음 M개 줄에 양방향 도로의 두 지점과 이동 시간이 주어진다.

다음 W개 줄에 웜홀의 출발 지점, 도착 지점, 감소 시간이 주어진다.

• 1 ≤ N ≤ 500
• 1 ≤ M ≤ 2,500
• 1 ≤ W ≤ 200
• 1 ≤ 이동 시간 ≤ 10,000
• 1 ≤ 감소 시간 ≤ 10,000

출력

각 테스트 케이스마다 시간이 되돌아갈 수 있으면 YES, 없으면 NO를 출력한다.

예제 입력 1

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 3 2
1 2 4
1 3 8
2 3 1
3 1 5
3 2 5

예제 출력 1

NO
YES