Cho đồ thị có hướng có trọng số gồm n đỉnh và m cung.

Tìm đường đi nhỏ nhất từ đỉnh s đến tất cả các đỉnh còn lại.

INPUT

Dòng đầu là 3 số nguyên dương: n, m, s (n ≤ ${10}^4$; m ≤ ${2.10}^5$; 1 ≤ s ≤ n)

m dòng tiếp theo, mỗi dòng gồm 3 số nguyên u, v, c cho biết có cung u-v với trọng số c. (1 ≤ u, v ≤ n; |c| ≤ ${10}^4$).

Lưu ý: trọng số có thể âm.

OUTPUT

Ghi ra n số trên cùng một dòng: số thứ i là độ dài đường đi ngắn nhất từ đỉnh s đến đỉnh i. Nếu không có đường đi từ s đến đỉnh i thì ghi ra -1.

Ví dụ:

Input

5 7 2
1 3 8
1 5 -7
4 1 12
2 5 8
2 4 5
3 5 1
5 4 -4

Output:

16 0 24 4 8 

Bài khó hơn