Một nhà thám hiểm đang khảo sát vùng đất mới gồm \(N\) địa điểm và \(M\) con đường một chiều nối giữa chúng. Mỗi con đường có một lượng năng lượng tiêu thụ nhất định (nếu dương) hoặc lượng năng lượng nạp lại từ các túi quà trên đường (nếu âm).

Hãy tìm lượng năng lượng tích lũy tối thiểu cần thiết để đi từ địa điểm xuất phát \(S\) đến tất cả các địa điểm khác trên bản đồ. Giả sử ban đầu lượng năng lượng tích lũy tại \(S\) bằng \(0\). Vùng đất này được đảm bảo không chứa các khu vực nạp năng lượng vô hạn (tức là không chứa chu trình âm).

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ả một con đường một chiều đi từ \(u\) đến \(v\) có lượng năng lượng thay đổi là \(w\).

Kết quả ra

• In ra \(N\) số nguyên trên một dòng, số thứ \(i\) là lượng năng lượng tích lũy nhỏ nhất để đi từ \(S\) đến địa điểm \(i\). Nếu không thể đi đến địa điểm \(i\), in ra \(-1\).

Ví dụ

Input

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

Output

0 5 3 4