Cho n địa điểm, giữa 2 địa điểm có thể có đường đi trực tiếp. Có tất cả m đường đi trực tiếp.

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

INPUT

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

m dòng tiếp theo, mỗi dòng gồm 3 số nguyên dương u, v, c cho biết có đường đi nối 2 địa điểm u và v với độ dài c. (1 ≤ u, v ≤ n; c ≤ ~10^4~).

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 điểm i. Nếu không có đường đi từ s đến điểm i thì ghi ra -1.

Ví dụ:

Input

5 7 2
1 3 8
1 5 7
1 4 12
2 5 11
2 4 5
3 5 16
5 4 4

Output:

16 0 24 5 9