変な将棋

ストーリー

将棋が好きなナツアカネ君は友達のアキアカネ君と将棋をしていました。 しかし、普通の将棋には飽きてしまったので、新しい駒を考えることにしました。

問題文

二人は縦横がそれぞれ$N$マスの将棋盤を持っています。 ナツアカネ君は新しい駒をうまく動かして敵の王将の場所に移動させようとしています。

将棋盤の上から$i$マス目、左から$j$マス目を$(i, j)$と表すと、$(A, B)$に新しい駒が、$(C, D)$に王将がそれぞれあります。 また、$M$個の動き方が存在し、新しい駒は一回の行動で今いる位置からいずれかの動きをすることができます。

$i$ $(1\leq i\leq M)$個目の動き方は$x_i$と$y_i$と$c_i$で表され、新しい駒を下へ$x_i$マス、右へ$y_i$マス動かせますが、ナツアカネ君には疲れ$c_i$が溜まってしまいます。

敵の王将は動きません。新しい駒を何回か行動させて敵の王将に重ねるとき、ナツアカネ君に溜まる最小の疲れを答えてください。 また、重ねることが不可能な場合には、そのことを伝えてください。

入力

N M
A B C D
x_1 y_1 c_1
x_2 y_2 c_2
⋮
x_M y_M c_M

出力

答えを1行で出力してください。最後に改行をしてください。

制約

• 入力はすべて整数で与えられる。
• $2\leq N\leq 100$
• $1\leq M\leq 10$
• $1\leq A, B, C, D\leq N$
• $-100\leq x_i\leq 100 (1\leq i\leq M)$
• $-100\leq y_i\leq 100 (1\leq i\leq M)$
• $1\leq c_i\leq 100 (1\leq i\leq M)$

サンプル

3 4
1 1 2 2
1 0 1
0 1 1
-1 0 1
0 -1 1

2

新しい駒は$(1, 1)$、王将は$(2, 2)$にいます。 新しい駒は隣接する四方向のマスに移動することができます。

以下の２通りの方法で最小の行動で王将に重ねることができます。

• 駒を$(1, 2)$に動かしたあと、$(2, 2)$に動かす。疲れが合計で2溜まる。
• 駒を$(2, 1)$に動かしたあと、$(2, 2)$に動かす。疲れが合計で2溜まる。

10 8
2 2 8 8
2 1 1
2 -1 2
1 2 3
1 -2 4
-1 2 5
-1 -2 6
-2 1 7
-2 -1 8

8

チェスのナイトのような動きができます。１番目の動きを２回、３番目の動きを２回することで疲れを$1\times 2 + 3\times 2 = 8$にできます。

10 1
1 1 2 2
100 0 100

-1

どこにも動くことができません。