Mạng lưới năng lượng của Bình gồm \(N\) nút phân phối và \(M\) kênh truyền dẫn một chiều. Kênh truyền dẫn nối từ \(u\) tới \(v\) tiêu hao hoặc giải phóng năng lượng \(w\). Bình muốn kiểm tra độ tiêu hao năng lượng tối ưu từ trạm nguồn \(S\) đến tất cả các nút khác trong hệ thống để điều chỉnh công suất sạc. Đồ thị đảm bảo không có vòng lặp giải phóng năng lượng vô hạn có thể đạt tới từ \(S\).

Đị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 3000\), \(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\)).

Định dạng đầu ra

• In ra \(N\) dòng, dòng thứ \(i\) biểu thị độ tiêu hao năng lượng tối thiểu từ \(S\) tới \(i\). Nếu không có đường đi đến nút \(i\), in ra INF.

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 2 1
1 2 5
2 3 -2

Output:

0
5
3

Giải thích:

• Khoảng cách đến nút 1: \(0\).
• Khoảng cách đến nút 2 (\(1 \to 2\)): \(5\).
• Khoảng cách đến nút 3 (\(1 \to 2 \to 3\)): \(5 + (-2) = 3\).