Vũ trụ Z có ~n~ hành tinh, các hành tinh được đánh số từ 1 đến ~n~. Một hệ thống gồm ~m~ đường dịch chuyển, đường dịch chuyển thứ ~k~ (~1 \le k \le m~) sẽ giúp di chuyển từ hành tinh ~i_k~ đến hành tinh ~j_k~ và mất chi phí là ~e(i_k, j_k)~. Một vụ nổ trong vũ trụ đã làm ảnh hưởng lớn đến tất cả các hành tinh, trừ hành tinh số 1. Hành tinh số 1 lên kế hoạch cứu hộ cho ~n - 1~ hành tinh còn lại.

Các nhà khoa học ở hành tinh số 1 đã tìm ra cách di chuyển giúp đội cứu hộ có thể di chuyển đến một hành tinh khác với chi phí nhỏ hơn. Cụ thể, với số nguyên không âm ~a~ mà các nhà khoa học thiết đặt, giả sử đội cứu hộ lần lượt di chuyển qua dãy gồm ~p~ hành tinh ~1 = x_1, x_2, ..., x_p~. Như vậy, đội cứu hộ sẽ phải sử dụng ~p - 1~ đường dịch chuyển, gọi ~s_1~ là tổng chi phí của ~p - 1~ đường dịch chuyển, gọi ~r_1~ là tổng chi phí của ~a~ đường dịch chuyển có chi phí lớn nhất trong ~p - 1~ đường dịch chuyển (nếu ~a > p - 1~ thì tính tổng chi phí của ~p - 1~ đường dịch chuyển), khi đó đội cứu hộ sẽ mất chi phí là ~s_1 - r_1~.

Về phía các hành tinh, các nhà khoa học cũng đã tính toán ra số nguyên không âm ~b~ dựa trên mức độ ảnh hưởng của vụ nổ để xác định được chi phí di chuyển của cư dân. Cụ thể, nếu cư dân hành tinh ~i~ phải di chuyển qua dãy gồm ~q~ hành tinh ~i = y_1, y_2, ..., y_q~, gọi ~s_2~ là tổng chi phí của ~q - 1~ đường dịch chuyển, gọi ~r_2~ là tổng chi phí của ~b~ đường dịch chuyển có chi phí nhỏ nhất trong ~q - 1~ đường dịch chuyển (nếu ~b > q - 1~ thì tính tổng chi phí của ~q - 1~ đường dịch chuyển), khi đó cư dân sẽ mất chi phí là ~s_2 + r_2~.

Chi phí để đội cứu hộ gặp được cư dân hành tinh ~i~ là tổng chi phí di chuyển của đội cứu hộ cộng với tổng chi phí của cư dân hành tinh ~i~ di chuyển để họ gặp được nhau.

Yêu cầu: Với mỗi hành tinh ~i~ (~2 \le i \le n~), hãy tính chi phí nhỏ nhất để đội cứu hộ xuất phát từ hành tinh 1 có thể gặp cư dân hành tinh ~i~.

Input

• Dòng đầu chứa bốn số nguyên ~n, m, a, b~;
• Dòng thứ ~k~ (~1 \le k \le m~) trong ~m~ dòng tiếp theo chứa ba số nguyên dương ~i_k, j_k, e(i_k, j_k)~, trong đó ~i_k \neq j_k \le n~ và ~e(i_k, j_k) \le 10^9~. Dữ liệu đảm bảo từ hành tinh ~i~ không có quá một đường dịch chuyển tới ~j~ và không tới chính nó.

Output

• Ghi ra thiết bị ra chuẩn gồm một dòng chứa ~n - 1~ số, số thứ ~i~ là chi phí nhỏ nhất để đội cứu hộ có thể gặp cư dân hành tinh ~i+1~, nếu đội cứu hộ không thể gặp được cư dân thì đưa ra số -1 tương ứng.

Sample Input 1

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

Sample Output 1

0 1 2

Giải thích:

Subtasks

• Subtask 1 (25 điểm): ~n \le 100; m \le 1000; a = b = 0~;
• Subtask 2 (25 điểm): ~n \le 100; m \le 1000; a = b = 1~;
• Subtask 3 (25 điểm): ~n \le 10^5; m \le 10^5; a = b = 0~;
• Subtask 4 (25 điểm): ~n \le 10^5; m \le 10^5; 0 \le a, b \le 3~;