Phát hiện vòng lợi nhuận bất thường

Bối cảnh và bài toán

Một đồ thị giao dịch có trọng số có thể âm. Chu trình tổng trọng số âm biểu diễn một vòng chi phí có thể giảm vô hạn.

Yêu cầu

Xác định đồ thị có chứa ít nhất một chu trình âm ở bất kỳ đâu hay không.

Input

Dòng đầu n, m; tiếp theo m cạnh có hướng u, v, w.

Output

In "YES" nếu có chu trình âm, ngược lại "NO".

Ràng buộc

• 1 <= n <= 2500
• 0 <= m <= 5000
• -10^9 <= w <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 100, m <= 300 | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

4 5
1 2 1
2 4 1
3 1 1
4 1 -3
4 3 -2

Output

YES

Giải thích. Còn cải thiện ở vòng thứ n là dấu hiệu tồn tại chu trình âm.

Ví dụ 2

Input

3 2
1 2 1
2 3 1

Output

NO

Giải thích. Còn cải thiện ở vòng thứ n là dấu hiệu tồn tại chu trình âm.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Cycle Finding. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.