Tèo thám hiểm một vùng đất vũ trụ kỳ bí gồm \(N\) tinh cầu và \(M\) cổng không gian một chiều. Khi đi qua mỗi cổng, thời gian của Tèo sẽ thay đổi một lượng \(w\) giây (nếu \(w\) âm, Tèo sẽ quay ngược thời gian).

Xuất phát từ tinh cầu xuất phát \(S\), hãy xác định xem Tèo có thể đi thám hiểm qua một chuỗi cổng và quay ngược thời gian vô hạn hay không (quay về quá khứ vô tận).

Định dạng đầu vào

• Dòng đầu chứa ba số nguyên \(N\), \(M\), \(S\) (\(1 \le N \le 1000\), \(0 \le M \le 2000\), \(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\)), biểu thị cổng nối từ \(u\) tới \(v\) thay đổi thời gian \(w\) giây.

Định dạng đầu ra

• In ra YES nếu tồn tại hành trình xuất phát từ \(S\) chứa vòng lặp thời gian âm vô tận. Ngược lại in ra NO.

Ràng buộc

• Subtask 1 (40% số điểm): \(N \le 100\), \(M \le 200\).
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input:

3 3 1
1 2 2
2 3 3
3 1 -6

Output:

YES

Giải thích: Chu kỳ âm \(1 \to 2 \to 3 \to 1\) có tổng trọng số là \(2 + 3 - 6 = -1 < 0\) và có thể đạt tới được từ tinh cầu xuất phát \(S=1\).