{"trustable":false,"sections":[{"title":"Statement","value":{"format":"MD","content":"\u003cp\u003eWhile exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ\u0027s farms comprises $N$ ($1 ≤ N ≤ 500$) fields conveniently numbered $1$ to $N$, $M$ ($1 ≤ M ≤ 2500$) paths, and $W$ ($1 ≤ W ≤ 200$) wormholes.\u003c/p\u003e\u003cp\u003eAs FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. \u003c/p\u003e\u003cp\u003eTo help FJ find out whether this is possible or not, he will supply you with complete maps to $F$ ($1 ≤ F ≤ 5$) of his farms. No paths will take longer than $10^4$ seconds to travel and no wormhole can bring FJ back in time by more than $10^4$ seconds.\u003c/p\u003e"}},{"title":"Input","value":{"format":"MD","content":"Line 1: A single integer, $F$. $F$ farm descriptions follow.\nLine 1 of each farm: Three space-separated integers respectively: $N, M$, and $W$.\n\u003cbr\u003eLines 2 to $(M+1)$ of each farm: Three space-separated numbers $S, E, T$ that describe, respectively: a bidirectional path between $S$ and $E$ that requires $T$ seconds to traverse. Two fields might be connected by more than one path.\n\u003cbr\u003eLines $(M+2)$ to $(M+W+1)$ of each farm: Three space-separated numbers $S, E, T$ that describe, respectively: A one way path from $S$ to $E$ that also moves the traveler back $T$ seconds."}},{"title":"Output","value":{"format":"MD","content":"Line 1 to $F$: For each farm, output `YES` if FJ can achieve his goal, otherwise output `NO`."}},{"title":"Sample","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3 3 1\n1 2 2\n1 3 4\n2 3 1\n3 1 3\n3 2 1\n1 2 3\n2 3 4\n3 1 8\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eNO\nYES\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\nFor farm 1, FJ cannot travel back in time.\nFor farm 2, FJ could travel back in time by the cycle $1 \\rightarrow 2 \\rightarrow 3 \\rightarrow 1$, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this."}}]}