Mô tả bài toán

John phát hiện ra nhiều hố sâu không gian trong trang trại của mình. Hố sâu có thể được coi là một loại cạnh có hướng đặc biệt, cho phép bạn quay trở lại một thời điểm trong quá khứ (tương đối so với trước khi bạn bước vào hố sâu).

Trang trại của John có:

• Các đường kết nối hai chiều giữa các ô đất (~paths~),
• Và hố sâu không gian là các cạnh đặc biệt một chiều.

John muốn sử dụng các hố sâu để quay ngược thời gian trước thời điểm khởi hành. John sẽ cung cấp cho bạn một bản đồ trang trại. Không có đường đi nào dẫn bạn đi xa hơn 10⁴ giây, và tất nhiên không có hố sâu nào giúp bạn quay ngược lại quá 10⁴ giây.

Định dạng đầu vào

• Dòng 1: Một số nguyên F, số lượng trang trại.
• Mỗi trang trại bao gồm:
  1. Dòng đầu tiên chứa ba số nguyên: n, m, w:
     • n: số lượng ô đất,
     • m: số đường kết nối hai chiều,
     • w: số hố sâu không gian.
  2. m dòng tiếp theo: Mỗi dòng chứa ba số nguyên s, e, t:
     • Đường kết nối hai chiều từ ô s đến ô e với chi phí thời gian là t giây.
  3. w dòng tiếp theo: Mỗi dòng chứa ba số nguyên s, e, t:
     • Hố sâu một chiều từ ô s đến ô e, cho phép quay ngược thời gian t giây.

Định dạng đầu ra

• Với mỗi trang trại:
  • In YES nếu John có thể đạt được mục tiêu của mình (sử dụng hố sâu để quay lại quá khứ).
  • In NO nếu không thể.

Ví dụ:

Input:

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

Output:

NO
YES