問題文

Pythonをお使いの場合は、PyPyでの提出もご検討ください。

$N$ 行 $N$ 列のマス目があります。上から $h$ 行目、左から $w$ 列目のマスを、マス $(h,w)$ と呼びます。

はじめA君はマス $(1,1)$ にいます。A君はマス $(N,N)$ を目指して移動します。

A君は現在いるマスの上下左右いずれかのマスに移動でき、この時移動料金が $1$ かかります。

B君はマス $(1,1)$ とマス $(N,N)$ 以外のマスから $M$ 個マスを選び、A君がマス $(h_i,w_i)$ に到達した際に

通行料金 $c_i$ を徴収することにしました。B君が選択しなかったマスに通行料金は発生しません。

しかしこれに納得できないA君はB君と交渉し、好きな時に一度だけ通行料金を支払わなくても良いことになりました。

A君がマス $(N,N)$ に移動するまでにかかる、移動料金と通行料金の総和の最小値を求めてください。

入力

$N\ M$
$h_1\ w_1\ c_1$
$h_2\ w_2\ c_2$
$\vdots$
$h_M\ w_M\ c_M$

・入力は全て整数である。
・$2 \le N \le 500$
・$1 \le M \le N^2-2$
・$1 \le h_i,w_i \le N$
・$1 \le c_i \le 10^9$
・$(h_i,w_i) \neq (1,1),(N,N)$
・$h_i=h_j$ かつ $w_i=w_j$ なる $i,j$ $(i \neq j)$ は存在しない。

出力

A君がマス $(N,N)$ に移動するまでにかかる、移動料金と通行料金の総和の最小値を出力してください。

サンプル

3 7
1 2 5
1 3 8
2 1 7
2 2 3
2 3 9
3 1 11
3 2 2

9

3 2
2 2 100
2 3 200

4

5 22
3 5 6949
3 3 7763
2 3 6013
2 2 9260
5 3 111
1 4 2477
1 2 1349
5 4 7141
2 4 4843
5 1 6378
1 5 8295
3 4 326
4 5 6162
3 2 9381
3 1 182
4 4 7878
2 1 8440
2 5 4872
4 2 8346
4 3 2296
4 1 3398
5 2 6

15165