Tìm chu trình

Trong một dự án cơ khí mới, FullHouse Dev được giao nhiệm vụ phân tích một hệ thống máy móc phức tạp. Họ cần kiểm tra xem liệu có tồn tại chu trình âm trong sơ đồ kết nối của hệ thống hay không, để đảm bảo tính ổn định của toàn bộ hệ thống.

Bài toán

Cho một đồ thị có hướng, nhiệm vụ của bạn là tìm ra xem đồ thị có chứa chu trình âm hay không, và đưa ra một ví dụ về chu trình đó nếu có.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số lượng đỉnh và cạnh. Các đỉnh được đánh số từ \(1,2,\ldots,n\).
• \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a\), \(b\) và \(c\): mô tả một cạnh từ đỉnh \(a\) đến đỉnh \(b\) với độ dài \(c\).

OUTPUT FORMAT:

• Nếu đồ thị chứa chu trình âm, in ra "YES" và các đỉnh trong chu trình theo đúng thứ tự.
• Nếu có nhiều chu trình âm, bạn có thể in ra bất kỳ chu trình nào.
• Nếu không có chu trình âm, in ra "NO".

Ràng buộc:

• \(1 \leq n \leq 2500\)
• \(1 \leq m \leq 5000\)
• \(1 \leq a,b \leq n\)
• \(-10^9 \leq c \leq 10^9\)

Ví dụ

INPUT

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

OUTPUT

YES
1 2 4 1

Giải thích

Trong ví dụ này, chu trình 1 → 2 → 4 → 1 có tổng độ dài là 1 + 1 + (-3) = -1 < 0, do đó đây là một chu trình âm.