問題文

しおむすび共和国には、町 $1$ から町 $N$ までの $N$ 個の町と、道路 $1$ から道路 $M$ までの $M$ 本の道路があります。道路 $i$ は $A_i$ と $B_i$ ($A_i < B_i$) を双方向に結んでいて、長さは $C_i$ です。

しおむすび共和国では、町 $i$ に着いてから町 $i$ を出発するまでに、しおむすびをちょうど $T_i$ 分間食べる必要があります。(町 $1$ を出発するときにもしおむすびを食べる必要がありますが、町 $N$ に到着した時に食べる必要はありません。)

同じ町を何度も通ることも可能で、そのたびにしおむすびを食べる必要があります。

また、町 $1$ を出発してからしおむすびを合計で $P$ 分間食べたとき、長さ $l$ の道路を $\lfloor \frac{l}{P} \rfloor$ 分で通ることができます。(制約下で $P=0$ で道を渡ることがないと証明できます。)

Liunxmetel 君は、自分が住む町 $1$ から、新プロランドがある町 $N$ におでかけに行こうと思っています。 Linuxmetel 君が、町 $N$ につくまでにかかる時間の最小値を求めなさい。

ただし、 Linuxmetel くんは道路以外を通って別の町に移動することはできません。また、町以外のところでしおむすびを食べることはありません。

入力

$N\ M$
$A_1\ B_1\ C_1$
$A_2\ B_2\ C_2$
　　$\vdots$
$A_M\ B_M\ C_M$
$T_1\ T_2\ \ldots\ T_N$

• 入力はすべて整数
• $2 \leq N\leq 100$
• $1 \leq M\leq\min\left(\frac{N(N-1)}{2},100\right)$
• $1 \leq A_i < B_i \leq N$
• $i \neq j$ ならば $(A_i, B_i) \neq (A_j, B_j)$
• $1 \leq C_i \leq 1000$
• $0 \leq T_i \leq 100$
• $T_1 \neq 0,T_N = 0$
• 与えられる入力データにおいては、町 $1$ から町 $N$ まで $0$ 個以上の町を通って移動できることが保証されている

出力

Linuxmetel 君が、町 $N$ につくまでにかかる時間の最小値を正整数で出力せよ。

また、最後に改行を出力せよ。

サンプル

2 1
1 2 10
1 0

11

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

8

6 15
2 6 202
1 2 185
3 6 978
2 3 976
3 4 445
1 6 795
1 5 951
2 4 626
4 5 265
1 4 501
1 3 685
2 5 899
5 6 766
3 5 923
4 6 343
46 19 23 75 48 0

63