Trong một hệ thống giao dịch thương mại giữa \(N\) trạm và \(M\) tuyến đường một chiều, mỗi tuyến đường có một mức thuế hoặc lợi nhuận chênh lệch \(w\) khi thực hiện trao đổi.

Hãy xác định xem bắt đầu từ trạm xuất phát \(S\), một thương nhân có thể thực hiện một chuỗi giao dịch tạo ra lợi nhuận vô hạn (tức là đi qua một chu trình âm để giảm tổng chi phí tích lũy xuống cực tiểu vô hạn) hay không.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(N, M\) và \(S\) (\(1 \le N \le 1000\), \(1 \le M \le 5000\), \(1 \le S \le N\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u, v, w\) (\(1 \le u, v \le N\), \(-1000 \le w \le 1000\)) mô tả tuyến giao dịch một chiều từ \(u\) đến \(v\) có chi phí \(w\).

Kết quả ra

• In ra YES nếu tồn tại một chu trình sinh lời vô hạn có thể đạt được từ \(S\), ngược lại in ra NO.

Ví dụ

Input

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

Output

YES