Xe đạp (Bicycles)

Nguồn: Codeforces

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

Đề bài

Có $n$ thành phố và $m$ con đường hai chiều. Con đường thứ $i$ nối $u_i$ với $v_i$ và có độ dài $w_i$.

Mỗi thành phố $i$ bán một chiếc xe đạp có hệ số chậm $s_i$. Nếu đi qua một cạnh dài $w$ bằng chiếc xe có hệ số $s$, thời gian cần thiết là

Bạn bắt đầu tại thành phố $1$, chưa có xe và không thể đi bộ. Bạn có thể mua bao nhiêu xe tùy ý; sau khi mua một chiếc xe, bạn có thể sử dụng lại chiếc xe đó ở các đoạn sau.

Hãy tìm thời gian nhỏ nhất để đến thành phố $n$.

Đề bảo đảm có thể đi từ thành phố $1$ đến mọi thành phố khác.

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 $u_i,v_i,w_i$.

Dòng cuối chứa $n$ số nguyên $s_1,s_2,\ldots,s_n$.

Hai thành phố có thể được nối bởi nhiều con đường khác nhau.

Output

In thời gian nhỏ nhất để đi từ thành phố $1$ đến thành phố $n$.

Subtask

Trong tất cả các Subtask: $2\le n\le1000$; $n-1\le m\le1000$; $1\le u_i,v_i\le n$; $u_i\ne v_i$; $1\le w_i\le10^5$; $1\le s_i\le1000$; từ thành phố $1$ có thể đi tới mọi thành phố.

• Subtask 1 — 10%: $s_1=s_2=\cdots=s_n$.
• Subtask 2 — 20%: Đồ thị là một cây, tức $m=n-1$.
• Subtask 3 — 30%: $n\le120$; $m\le300$.
• Subtask 4 — 40%: Không có điều kiện bổ sung.

Ví dụ

Input

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

Output

19

Giải thích

Trong dữ liệu mẫu, lựa chọn các xe phù hợp trên đường đi cho thời gian nhỏ nhất bằng $19$.