Mua vé hòa nhạc (Buy a Ticket)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ thành phố và $m$ tuyến tàu hai chiều. Tuyến thứ $i$ nối $v_i$ với $u_i$ và tốn $w_i$ xu cho mỗi lần đi qua.

Ban nhạc biểu diễn tại mọi thành phố. Giá vé xem hòa nhạc tại thành phố $i$ là $a_i$ xu.

Với một người đang sống ở thành phố $i$, người đó có thể:

• ở lại thành phố $i$ và mua vé tại đó; hoặc
• đi đến một thành phố $j$, mua vé tại $j$, rồi quay trở lại thành phố $i$.

Hãy tính chi phí nhỏ nhất cho người ở mỗi thành phố.

Input

Dòng đầu chứa hai số nguyên $n,m$.

Trong $m$ dòng tiếp theo, mỗi dòng chứa $v_i,u_i,w_i$, mô tả một tuyến tàu hai chiều.

Dòng cuối chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$.

Không có hai tuyến tàu nối cùng một cặp thành phố.

Output

In $n$ số nguyên. Số thứ $i$ là tổng chi phí nhỏ nhất mà một người bắt đầu ở thành phố $i$ phải trả để đi xem hòa nhạc và quay về thành phố $i$ nếu đã rời thành phố.

Subtask

Trong tất cả các Subtask: $1\le v_i,u_i\le n$; $v_i\ne u_i$; $1\le w_i,a_i\le10^{12}$; không có hai tuyến tàu nối cùng một cặp thành phố.

• Subtask 1 — 20% — 0.50 giây: $2\le n\le100$; $1\le m\le500$.
• Subtask 2 — 30% — 1.00 giây: $2\le n\le5000$; $1\le m\le10^4$.
• Subtask 3 — 50% — 2.00 giây: $2\le n\le2\cdot10^5$; $1\le m\le2\cdot10^5$.

Ví dụ

Input

4 2
1 2 4
2 3 7
6 20 1 25

Output

6 14 1 25

Giải thích

Ở thành phố $1$, mua vé ngay hết $6$ nên không cần đi đâu. Ở thành phố $2$, phương án tốt hơn là đi tới thành phố $3$, mua vé giá $1$ rồi quay lại; tổng chi phí là $7+1+7=15$, nhưng đi tới thành phố $1$ rồi mua vé có chi phí $4+6+4=14$, nên đáp án là $14$. Thành phố $3$ mua vé tại chỗ với giá $1$.