📖 Bài giảng & lời giải: đây là Bài tập 8 trong bài giảng Bài 29: Đường đi ngắn nhất trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Một sàn đổi tiền có $n$ loại tiền (đánh số từ 1 tới $n$) và $m$ giao dịch. Giao dịch thứ $i$ đổi từ loại $u_i$ sang loại $v_i$ với "chi phí" $w_i$; chi phí có thể âm, nghĩa là được lời.

Nếu tồn tại một vòng giao dịch xuất phát từ một loại tiền nào đó và quay về chính loại tiền đó với tổng chi phí âm (đi mãi thì lời vô hạn), in YES, ngược lại in NO. Vòng đó có thể bắt đầu ở bất kỳ loại tiền nào.

Dữ liệu vào

• Dòng 1: hai số nguyên $n, m$ ($1 \le n \le 500$, $0 \le m \le 5000$).
• $m$ dòng tiếp theo, dòng thứ $i$ gồm ba số nguyên $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n$, $|w_i| \le 10^9$).

Kết quả

In YES nếu có vòng giao dịch với tổng chi phí âm, ngược lại in NO.

Sample Input

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

Sample Output

YES

Note

Vòng 2 → 3 → 2 có tổng chi phí $-2 + 1 = -1 \lt 0$.