1370 - 시간을 거슬러 올라가는 웜홀

Time Limit: 1s Memory Limit: 128MB

Submissions: 102 Solved: 11
Description

WithCS 농장 아저씨는 농장을 둘러보던 중에 다수의 웜홀을 발견했습니다.

발견한 웜홀은 매우 놀라운 것인데요, 시간을 거슬러 단방향으로 이동하게 됩니다. 잘 활용하면 오늘 출발해서 어제 도착할 수 있는 것이죠.

각각의 농장은 N(1~500)개의 논으로 구성되고 1부터 N까지 순서 번호가 부여됩니다. 그리고 M(1~2500)개의 길이 있으며, W(1~200)개의 웜홀이 있습니다.

WithCS 아저씨는 시간 여행자에 대한 로망을 가지고 있었기에 다음과 같은 계획을 세웠습니다. 어떤 논에서 출발해서 과거의 시점에서 다시 출발지로 돌아오는 경로를 짜는 것입니다. 잘 한다면 자기 자신과 만날 수 있겠죠?

WithCS 아저씨의 로망을 이루어주기 위해 F (1~5)개의 농장을 검사해서 아저씨의 계획이 가능한지 조사해봅시다. 단, 어떠한 길도 10,000초의 시간이 소요되지 않으며, 어떠한 웜홀도 10,000초의 시간을 얻을 수 있지 않습니다.

Input

* Line 1 : 단일 정수 F (농장의 수)

각각의 농장에 대해

   * Line 1 : 3개의 정수 N, M, W

        - N : 논의 수

        - M : 길의 수

        - W : 웜홀의 수

    * Line 2 ~ M + 1 : 3개의 정수, S, E, T

        - S : (양방향) 길의 시작 지점

        - E : (양방향) 길의 종료 지점

        - T : 길을 이용한 이동으로 소요되는 시간

    * Line M+2 ~ M+W+1 : 3개의 정수, S, E, T

        - S : (단방향) 웜홀의 시작 지점

        - E : (단방향) 웜홀의 종료 지점

        - T : 웜홀을 이용한 이동으로 얻는 시간

Output

* Line 1 ~ F : 각각의 농장에 대해 WithCS 아저씨의 목표 달성 여부를 문자열로 표시

    - 성공 시 : "YES"

    - 실패 시 : "NO"

Sample Input
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
Sample Output
NO
YES
Hint

첫번째 농장의 경우, WithCS 아저씨는 시간을 거슬러 올라갈 수 없습니다.

두번째 농장의 경우, 1-길->2-길->3-웜홀->1 을 이용하여 이동하게 되면 1초의 시간을 거슬러 올라갈 수 있습니다! 오! 이런 신기한일이.. 이 과정을 계속 반복하면 모든 밭을 시간을 얻으면서 감시할 수 있습니다.

(추가) 길의 경우 양방향으로 이동 가능하며, 웜홀의 경우 단방향으로만 이동 가능합니다.