[class4] (백준 1865) 웜홀

문제

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), 도로의 개수 M(1 ≤ M ≤ 2500), 웜홀의 개수 W(1 ≤ W ≤ 200)이 주어진다. 그리고 두 번째 줄부터 M+1번째 줄에 도로의 정보가 주어지는데 각 도로의 정보는 S, E, T 세 정수로 주어진다. S와 E는 연결된 지점의 번호, T는 이 도로를 통해 이동하는데 걸리는 시간을 의미한다. 그리고 M+2번째 줄부터 M+W+1번째 줄까지 웜홀의 정보가 S, E, T 세 정수로 주어지는데 S는 시작 지점, E는 도착 지점, T는 줄어드는 시간을 의미한다. T는 10,000보다 작거나 같은 자연수 또는 0이다.

두 지점을 연결하는 도로가 한 개보다 많을 수도 있다. 지점의 번호는 1부터 N까지 자연수로 중복 없이 매겨져 있다.

출력

TC개의 줄에 걸쳐서 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 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

힌트

W3sicHJvYmxlbV9pZCI6IjE4NjUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZGNcdWQ2NDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjU0Y1x1YjI5NCAyMDIwXHViMTQ0LCBcdWJjMzFcdWM5MDBcdWM3NzRcdWIyOTQgXHVjNmQ0XHViNGRjXHViMDk4XHViNzdjXHVjNzU4IFx1ZDU1YyBcdWFkNmRcdWJiZmNcdWM3NzRcdWIyZTQuIFx1YzZkNFx1YjRkY1x1YjA5OFx1Yjc3Y1x1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzljMFx1YzgxMFx1Yzc3NCBcdWM3ODhcdWFjZTAgTlx1YWMxY1x1Yzc1OCBcdWM5YzBcdWM4MTAgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IE1cdWFjMWNcdWM3NTggXHViM2M0XHViODVjXHVjNjQwIFdcdWFjMWNcdWM3NTggXHVjNmRjXHVkNjQwXHVjNzc0IFx1Yzc4OFx1YjJlNC4gKFx1YjJlOCBcdWIzYzRcdWI4NWNcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzc0IFx1YzVjNlx1YzczY1x1YmE3MCBcdWM2ZGNcdWQ2NDBcdWM3NDAgXHViYzI5XHVkNWE1XHVjNzc0IFx1Yzc4OFx1YjJlNC4pIFx1YzZkY1x1ZDY0MFx1Yzc0MCBcdWMyZGNcdWM3OTEgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YjNjNFx1Y2MyOSBcdWM3MDRcdWNlNThcdWI4NWMgXHVhYzAwXHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWM3NzhcdWIzNzAsIFx1ZDJiOVx1Yzc3NFx1ZDU1OFx1YWM4Y1x1YjNjNCBcdWIzYzRcdWNjMjlcdWM3NDQgXHVkNTU4XHVhYzhjIFx1YjQxOFx1YmE3NCBcdWMyZGNcdWM3OTFcdWM3NDQgXHVkNTU4XHVjNjAwXHVjNzQ0IFx1YjU0Y1x1YmNmNFx1YjJlNCBcdWMyZGNcdWFjMDRcdWM3NzQgXHViNGE0XHViODVjIFx1YWMwMFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzZkY1x1ZDY0MCBcdWIwYjRcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjMmRjXHVhY2M0XHVhYzAwIFx1YWM3MFx1YWZiOFx1Yjg1YyBcdWFjMDRcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTU4XHVjNWVjXHViM2M0IFx1Yzg4Ylx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVhYzA0IFx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWI5ZTRcdWM2YjAgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1YmMzMVx1YzkwMFx1Yzc3NFx1YjI5NCBcdWQ1NWMgXHVhYzAwXHVjOWMwIFx1YWQ4MVx1YWUwOFx1Yzk5ZFx1YzVkMCBcdWJlNjBcdWM4NGNcdWIyZTQuJm5ic3A7XHVkNTVjJm5ic3A7XHVjOWMwXHVjODEwXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1Yzc0NCBcdWQ1NThcdWM1ZWNcdWMxMWMgXHVjMmRjXHVhYzA0XHVjNWVjXHVkNTg5XHVjNzQ0IFx1ZDU1OFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWM1ZWMgXHViMmU0XHVjMmRjIFx1Y2Q5Y1x1YmMxY1x1Yzc0NCBcdWQ1NThcdWM2MDBcdWIzNTggXHVjNzA0XHVjZTU4XHViODVjIFx1YjNjY1x1YzU0NFx1YzY1NFx1Yzc0NCBcdWI1NGMsIFx1Y2Q5Y1x1YmMxY1x1Yzc0NCBcdWQ1NThcdWM2MDBcdWM3NDQgXHViNTRjXHViY2Y0XHViMmU0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWI0MThcdWIzY2NcdWM1NDRcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YWMwMCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjNWM2XHViMjk0XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC4gXHVjNWVjXHViN2VjXHViZDg0XHVjNzQwIFx1YmMzMVx1YzkwMFx1Yzc3NFx1Yjk3YyBcdWIzYzRcdWM2NDAgXHVjNzc0XHViN2YwIFx1Yzc3Y1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NWNcdWM5YzAgXHViZDg4XHVhYzAwXHViMmE1XHVkNTVjXHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUQygxICZsZTsgVEMgJmxlOyA1KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBUQ1x1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWFjMDAgXHVjYzI4XHViODQwXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzljMFx1YzgxMFx1Yzc1OCBcdWMyMTggTigxICZsZTsgTiAmbGU7IDUwMCksIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMTggTSgxICZsZTsgTSAmbGU7IDI1MDApLCBcdWM2ZGNcdWQ2NDBcdWM3NTggXHVhYzFjXHVjMjE4IFcoMSAmbGU7IFcgJmxlOyAyMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE0rMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2M0XHViODVjXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAgXHVhYzAxIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgUywgRSwgVCBcdWMxMzggXHVjODE1XHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gU1x1YzY0MCBFXHViMjk0IFx1YzVmMFx1YWNiMFx1YjQxYyBcdWM5YzBcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4LCBUXHViMjk0IFx1Yzc3NCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkMWI1XHVkNTc0IFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIE0rMlx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTStXKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIFx1YzZkY1x1ZDY0MFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgUywgRSwgVCBcdWMxMzggXHVjODE1XHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCBTXHViMjk0IFx1YzJkY1x1Yzc5MSBcdWM5YzBcdWM4MTAsIEVcdWIyOTQgXHViM2M0XHVjYzI5IFx1YzljMFx1YzgxMCwgVFx1YjI5NCBcdWM5MDRcdWM1YjRcdWI0ZGNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gVFx1YjI5NCAxMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMTggXHViNjEwXHViMjk0IDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWM5YzBcdWM4MTBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWQ1NWMgXHVhYzFjXHViY2Y0XHViMmU0IFx1YjljZVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM5YzBcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWM3OTBcdWM1ZjBcdWMyMThcdWI4NWMgXHVjOTExXHViY2Y1IFx1YzVjNlx1Yzc3NCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRDXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHViOWNjXHVjNTdkXHVjNWQwIFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM5MDRcdWM1YjRcdWI0ZTRcdWJhNzRcdWMxMWMgXHVjZDljXHViYzFjIFx1YzcwNFx1Y2U1OFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MjRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YmE3NCBZRVMsIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YmE3NCBOT1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTg2NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ildvcm1ob2xlcyIsImRlc2NyaXB0aW9uIjoiPHA+V2hpbGUgZXhwbG9yaW5nIGhpcyBtYW55IGZhcm1zLCBGYXJtZXIgSm9obiBoYXMgZGlzY292ZXJlZCBhIG51bWJlciBvZiBhbWF6aW5nIHdvcm1ob2xlcy4gQSB3b3JtaG9sZSBpcyB2ZXJ5IHBlY3VsaWFyIGJlY2F1c2UgaXQgaXMgYSBvbmUtd2F5IHBhdGggdGhhdCBkZWxpdmVycyB5b3UgdG8gaXRzIGRlc3RpbmF0aW9uIGF0IGEgdGltZSB0aGF0IGlzIEJFRk9SRSB5b3UgZW50ZXJlZCB0aGUgd29ybWhvbGUhIEVhY2ggb2YgRkomIzM5O3MgZmFybXMgY29tcHJpc2VzIE4gKDEgJmx0Oz0gTiAmbHQ7PSA1MDApIGZpZWxkcyBjb252ZW5pZW50bHkgbnVtYmVyZWQgMS4uTiwgTSAoMSAmbHQ7PSBNICZsdDs9IDI1MDApIHBhdGhzLCBhbmQgVyAoMSAmbHQ7PSBXICZsdDs9IDIwMCkgd29ybWhvbGVzLjxcL3A+XHJcblxyXG48cD5BcyBGSiBpcyBhbiBhdmlkIHRpbWUtdHJhdmVsaW5nIGZhbiwgaGUgd2FudHMgdG8gZG8gdGhlIGZvbGxvd2luZzogc3RhcnQgYXQgc29tZSBmaWVsZCwgdHJhdmVsIHRocm91Z2ggc29tZSBwYXRocyBhbmQgd29ybWhvbGVzLCBhbmQgcmV0dXJuIHRvIHRoZSBzdGFydGluZyBmaWVsZCBhIHRpbWUgYmVmb3JlIGhpcyBpbml0aWFsIGRlcGFydHVyZS4gUGVyaGFwcyBoZSB3aWxsIGJlIGFibGUgdG8gbWVldCBoaW1zZWxmIDopIC48XC9wPlxyXG5cclxuPHA+VG8gaGVscCBGSiBmaW5kIG91dCB3aGV0aGVyIHRoaXMgaXMgcG9zc2libGUgb3Igbm90LCBoZSB3aWxsIHN1cHBseSB5b3Ugd2l0aCBjb21wbGV0ZSBtYXBzIHRvIEYgKDEgJmx0Oz0gRiAmbHQ7PSA1KSBvZiBoaXMgZmFybXMuICZuYnNwO05vIHBhdGhzIHdpbGwgdGFrZSBsb25nZXIgdGhhbiAxMCwwMDAgc2Vjb25kcyB0byB0cmF2ZWwgYW5kIG5vIHdvcm1ob2xlIGNhbiBicmluZyBGSiBiYWNrIGluIHRpbWUgYnkgbW9yZSB0aGFuIDEwLDAwMCBzZWNvbmRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXIsIEYuIEYgZmFybSBkZXNjcmlwdGlvbnMgZm9sbG93LjxcL2xpPlxyXG5cdDxsaT5MaW5lIDEgb2YgZWFjaCBmYXJtOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgcmVzcGVjdGl2ZWx5OiBOLCBNLCBhbmQgVzxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5NKzEgb2YgZWFjaCBmYXJtOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZWQgbnVtYmVycyAoUywgRSwgVCkgdGhhdCBkZXNjcmliZSwgcmVzcGVjdGl2ZWx5OiBhIGJpZGlyZWN0aW9uYWwgcGF0aCBiZXR3ZWVuIFMgYW5kIEUgdGhhdCByZXF1aXJlcyBUIHNlY29uZHMgdG8gdHJhdmVyc2UuIFR3byBmaWVsZHMgbWlnaHQgYmUgY29ubmVjdGVkIGJ5IG1vcmUgdGhhbiBvbmUgcGF0aC48XC9saT5cclxuXHQ8bGk+TGluZXMgTSsyLi5NK1crMSBvZiBlYWNoIGZhcm06IFRocmVlIHNwYWNlLXNlcGFyYXRlZCBudW1iZXJzIChTLCBFLCBUKSB0aGF0IGRlc2NyaWJlLCByZXNwZWN0aXZlbHk6IEEgb25lIHdheSBwYXRoIGZyb20gUyB0byBFIHRoYXQgYWxzbyBtb3ZlcyB0aGUgdHJhdmVsZXIgYmFjayBUIHNlY29uZHMuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmVzIDEuLkY6IEZvciBlYWNoIGZhcm0sIG91dHB1dCAmcXVvdDtZRVMmcXVvdDsgaWYgRkogY2FuIGFjaGlldmUgaGlzIGdvYWwsIG90aGVyd2lzZSBvdXRwdXQgJnF1b3Q7Tk8mcXVvdDsgKGRvIG5vdCBpbmNsdWRlIHRoZSBxdW90ZXMpLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

 

 

 

 

 

#include <iostream> 
#include <vector>
#include <cstring>
using namespace std;
const int INF = 2000000000;
string IsAble()
{
    int n, m, w;
    vector<pair<int, int>> load[501];
    cin >> n >> m >> w;
    int s, e, t;
    for (int i = 0; i < m; i++)
    {
        cin >> s >> e >> t;
        bool check = false;
        load[s].push_back({ e,t });
        load[e].push_back({ s,t });
    }
    for (int i = 0; i < w; i++)
    {
        cin >> s >> e >> t;
        load[s].push_back({ e,t * (-1) });
    }

    int value[501];
    for (int i = 1; i <= n; i++)
    {
        value[i] = INF;
    }
    value[1] = 0;
    for (int k = 0; k < n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (auto j = load[i].begin(); j < load[i].end(); j++)
            {
                int next = j->first;
                int d = j->second;
                if (value[i] + d < value[next])
                {
                    value[next] = value[i] + d;
                    if (k == n - 1)
                    {
                        return "YES";
                    }
                }
            }
        }
    }
    return "NO";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tc;
    cin >> tc;
    while (tc-- > 0)
    {
        cout << IsAble() << "\n";
    }
    return 0;
}