Khi mua xiên que về, Suika nhận ra là vẫn chưa có rượu. Có ~n~ cửa hàng bán rượu và có ~m~ con đường nối trực tiếp giữa 2 cửa hàng nào đó. Việc mua rượu ở cửa hàng ~i~ sẽ tốn ~a_i~ sức lực, việc đi qua con đường thứ ~i~ sẽ tốn ~w_i~ sức lực. Hỏi với mỗi cửa hàng, nếu Suika xuất phát từ cửa hàng đó thì để mua rượu và quay lại đúng cửa hàng đó sẽ tốn bao nhiêu sức lực, nói cách khác với mỗi cửa hàng ~i~, hãy tìm với ~d(i, j)~ là đường đi ngắn nhất giữa cửa hàng ~i~ và ~j~.

Input

• Dòng đầu tiên gồm số tự nhiên ~1 \le n \le 10^5~ và ~1 \le m \le 10^5~.
• ~m~ dòng tiếp theo gồm 3 số nguyên ~u_i~, ~v_i~, ~w_i~ ~(1 \le u_i, v_i \le n, 1 \le w_i \le 10^9 )~, đảm bảo không có khuyên và cạnh lặp.
• Dòng tiếp theo gồm ~n~ nguyên ~1 \le a_i \le 10^9~.

Output

• In ra ~n~ số tương ứng với ~n~ cửa hàng.

Sample Test

Input:

3 3
1 2 1
2 3 1
1 3 1
30 10 20

Output:

12 10 12