존이 농장을 둘러보니 많은 벌레 구멍이 있음을 알았다. 이 구멍은 매우 특이하다. 왜냐하면 그것은 한 방향 길이고 이 구멍으로 들어가기 이 전 시간으로 도착지에 데려다 준다. (주:이 부분 영어 번역을 제대로 못해서 한 참을 헤매었습니다. 이 구멍은 타임머신 구멍으로 이해)

농장은 N ( 1..500 ) 개의 필드(노드)로 구성되어 있고 , M ( 1<= M <= 2500 ) 개의 패스 그리고 W ( 1 <= W <= 200 ) 개의 구멍으로 이루어져 있다.

존은 시간을 끔찍히 아끼는 사람이라 아래와 같은 여행을 하고 싶어한다.

어떤 필드에서 시작한다. 어떤 패스와 벌레 구멍을 여행한 후 그가 여행을 시작한 곳으로 돌아와야 한다. 단 출발한 시각 이전시간에 도착해야 한다. 아마 자신이 자신을 만날수 도 있다.:)

당신에게 완전한 F ( 1 <= F <= 5 )개의 맵을 제공되고 어떤 길도 10,000 초 보다 더 길지는 않고 , 그리고 어떤 구멍도 되돌아 올 시간이 10,000 초들 넘지는 않는다.

입력

• 첫 줄: 농장 의 수 F , 다음 줄 부터 F 개의 농장 정보가 주어진다.
• 각 농장의 첫 줄: 세 개의 정수 N , M , W N 은 필드 수(노드) , M 은 일반적인 길의 수 , W 는 구멍의 수
• 각 농장의 2 .. M+1 줄: 다음 S,E,T 가 주어진다. S 에서 E 사이의 양방향 길이고 이동하는데 T 초 소요된다. 두 필드는 한 패스 이상 연결될 수 도 있다.
• 각 농장의 M+2 .. M+W+1 줄 : S,E,T 가 주어진다. S 에서 E 로 한 방향 길이고 , T 초 시간을 거슬러서 도착지에 도착한다.

출력

입출력 예

입력

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

입출력 보충

-농장 2 에서 , 존은 제시간에 1 -> 2 -> 3 -> 1 로 여행을 하면 출발 시각 보다 1 초 빨리 도착할 수 있다. 어떤 위치에서 출발해도 마찬가지이다.

출처: USACO 2006 December Gold