問題文

しおむすび共和国には、町 $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 くんは道路以外を通って別の町に移動することはできません。また、町以外のところでしおむすびを食べることはありません。

入力

$NM$
$A_1{B}_1{C}_1$
$A_2{B}_2{C}_2$
　　$⋮$
$A_M{B}_M{C}_M$
$T_1{T}_2\dots T_N$

• 入力はすべて整数
• $2\le N\le 100$
• $1\le M\le min(\frac{N(N-1)}{2},100)$
• $1\le A_i<B_i\le N$
• $i\ne j$ ならば $(A_i,B_i)\ne (A_j,B_j)$
• $1\le C_i\le 1000$
• $0\le T_i\le 100$
• $T_1\ne 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