Bellman-Ford: Truy vết Chu trình Âm

Mô tả bài toán

Cho một đồ thị có hướng gồm N đỉnh và M cạnh có trọng số (trọng số có thể âm). Hãy kiểm tra xem đồ thị có chứa chu trình trọng số âm hay không. Nếu có, hãy tìm và in ra các đỉnh thuộc một chu trình âm bất kỳ theo đúng thứ tự duyệt.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Input

• Dòng đầu tiên gồm 2 số nguyên N, M (1 ≤ N ≤ 2500, 1 ≤ M ≤ 5000).
• M dòng tiếp theo, mỗi dòng gồm 3 số nguyên u, v, w biểu thị cạnh có hướng từ u đến v với trọng số w (1 ≤ u, v ≤ N, -10⁹ ≤ w ≤ 10⁹).

Output

• Nếu không có chu trình âm, in ra NO.
• Nếu có, dòng đầu in ra YES, dòng thứ hai in ra dãy các đỉnh tạo thành chu trình (bắt đầu và kết thúc tại cùng một đỉnh, thể hiện chu trình khép kín).

Ràng buộc

• Thời gian: 1.0s. Bộ nhớ: 256MB.

Ví dụ 1