~dwuy~ hiện sống ở thành phố XYZ gồm ~n~ góc đường và ~m~ con đường, con đường thứ i nối góc đường ~u_i~ và ~v_i~, tốn ~c_i~ giây để đi hết con đường. Tại thành phố này còn có ~k~ cô người yêu của cậu. ~dwuy~ sống tại góc đường ~1~ và cô người yêu thứ ~i~ sống tại ngôi nhà ở góc đường ~x_i~.

Mỗi góc đường ở thành phố XYZ sẽ có một trụ đèn giao thông có hai màu xanh và đỏ. Nếu tín hiệu đèn đang là màu đỏ thì người đi đường sẽ phải dừng lại cho đến khi đèn giao thông chuyển sang màu xanh. Các trụ đèn đều có thời gian dừng đèn đỏ là ~R~ và thời gian cho đèn xanh là ~G~. Thời gian trên trụ đèn sẽ đếm ngược từ ~R~ giây đèn đỏ về ~1~ sau đó chuyển sang ~G~ giây đèn xanh, và ngược lại. Đèn xanh và đỏ sẽ hiện xen kẽ nhau ~R~ giây đèn đỏ xong đến ~G~ giây đèn xanh xong đến ~R~ giây đèn đỏ...

Tại thời điểm bắt đầu (thời điểm ~0~) trụ đèn tại góc đường thứ ~i~ sẽ là đèn xanh với ~t_i~ thời gian đếm ngược.

Mỗi ngày ~dwuy~ đều sẽ đến thăm ~k~ cô người yêu, nhưng thật không may hôm nay ~dwuy~ có hẹn với cô người yêu mới quen nên phải dành cả ngày cho cô ấy. Vì vậy ~dwuy~ chỉ có thể đến thăm duy nhất một cô trong ~k~ cô người yêu. Dữ liệu đảm bảo ~dwuy~ có đi đến mọi góc đường.

Yêu cầu:

Là bạn thân của ~dwuy~, bạn hãy giúp ~dwuy~ tính thời gian nhanh nhất để thăm cô người yêu thứ ~i~ (~1 \leq i \leq k~) và trở về nhà. Thời điểm ~dwuy~ bắt đầu đi từ nhà được tính là thời điểm ~0~.

Input

• Dòng đầu chứa năm số nguyên ~n, m, k, G, R~ — số góc đường, số con đường, số cô người yêu, thời gian mà ~dwuy~ phải chờ đen xanh và đỏ (~1 \leq k < n \leq 5 \times 10^4~, ~1 \leq m \leq 10^5~, ~1 \leq G \leq 20~, ~0 \leq R \leq 20~).

• Dòng thứ hai chứa ~k~ số nguyên ~x_1, x_2, \cdots, x_k~ — nơi ở của các cô người yêu của ~dwuy~ (~1 \leq x_i \leq n~).

• ~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i, v_i, c_i~ mô tả một cạnh của đồ thị (~1 \leq u_i, v_i \leq n~, ~1 \leq c_i \leq 10^9~).

• Dòng cuối cùng chứa ~n~ số nguyên ~t_1, t_2, \cdots, t_n~ — số giây đèn xanh ở mỗi góc đường tại thời điểm ~0~ (~1 \leq t_i \leq G~).

Output

Trên một dòng, in ra ~k~ số nguyên ~ans_1, ans_2, \cdots, ans_k~ lần lượt là thời gian nhanh nhất để thăm từng cô người yêu và trở về nhà.

Scoring

• Subtask 1 (~20\%~): ~R = 0~.

• Subtask 2 (~30\%~): ~1 \leq k \leq 10~.

• Subtask 3 (~50\%~): Không có ràng buộc gì thêm.

Sample Input 1

6 8 5 6 0
2 3 4 5 6
1 2 6
2 3 6
1 4 1
2 5 2
5 6 4
6 2 4
2 4 4
2 6 6
1 4 6 2 4 4

Sample Output 1

10 22 2 14 18

Sample Input 2

6 8 2 4 5
2 3
6 2 3
6 4 2
6 5 1
1 4 6
1 5 7
2 3 5
2 4 4
4 5 1
4 3 1 3 2 3

Sample Output 2

23 41