Cho một đồ thị vô hướng liên thông có trọng số ~n~ đỉnh, ~m~ cạnh. Cạnh thứ ~i~ có trọng số là ~weight(i)~. Định nghĩa cost của 1 đường đi qua các cạnh ~e_1, e_2, ..., e_k~ là:

~k \times X + \sum_{i=1}^{k} weight(e_i) - max(weight(e_1), ..., weight(e_k)) + min(weight(e_1), ..., weight(e_k))~.

Tìm đường đi có cost nhỏ nhất từ ~S~ đến ~n - 1~ đỉnh còn lại.

Input

• Dòng đầu tiên ~4~ số nguyên ~n, m, S, X~ ~(1 \le n, m \le 2 \times 10^5, 1 \le S \le n, 1 \le X \le 10^9)~.

• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên ~u,v,w~ lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~ ~(1 \le u, v \le n, u \ne v, 1 \le w \le 10^9)~.

Output

• In ra ~n - 1~ số nguyên là kết quả cần tìm. Các khoảng cách được in theo thứ tự đỉnh tăng dần.

Subtask

• ~20\%~ số test có ~1 \le n, m \le 10~.

• ~20\%~ số test khác có ~1 \le n, m \le 100~.

• ~20\%~ số test khác có ~m = n~.

• ~40\%~ số test còn lại không có điều kiện gì thêm.

Sample Input 1

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

Sample Output 1

7 9 7