Description

There is an $m \times m$ chessboard. Each cell on the board may be red, yellow, or colorless. You need to go from the top-left corner of the board to the bottom-right corner.

At any moment, the cell you stand on must be colored (not colorless). You can move only in four directions: up, down, left, and right. When you move from one cell to another, if the two cells have the same color, you do not need to spend any coins; if the colors are different, you need to spend $1$ coin.

In addition, you can spend $2$ coins to cast a spell to temporarily change the next colorless cell into a color you choose. But this spell cannot be used consecutively, and its duration is short. That is, if you use this spell and step onto this temporarily colored cell, you cannot use the spell again; only when you leave this position and step onto a cell that originally has a color can you use the spell again. When you leave the cell that was made colored by the spell, it reverts to colorless.

Now you need to go from the top-left corner to the bottom-right corner of the board. Find the minimum number of coins required.

Input Format

The first line contains two positive integers $m, n$, separated by a space, which denote the size of the board and the number of colored cells, respectively.

The next $n$ lines each contain three integers $x, y, c$, indicating that the cell at coordinates $(x,y)$ has color $c$.

Here, $c=1$ means yellow, and $c=0$ means red. Adjacent numbers are separated by a space. The top-left corner has coordinates $(1, 1)$, and the bottom-right corner has coordinates $( m, m)$.

All other cells on the board are colorless. It is guaranteed that the top-left corner $(1, 1)$ is colored.

Output Format

Output a single integer, the minimum number of coins required. If it is impossible to reach the destination, output -1.

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

8

5 5
1 1 0
1 2 0
2 2 1
3 3 1
5 5 0

-1

Hint

Explanation for Sample 1

The board’s colors are as shown in the table below, where blank cells are colorless.

Start from $(1,1)$ and move to $(1,2)$ without spending coins.

Move from $(1,2)$ down to $(2,2)$, spending $1$ coin.

Cast the spell at $(2,2)$ to make $(2,3)$ yellow, spending $2$ coins.

Move from $(2,2)$ to $(2,3)$ without spending coins.

Move from $(2,3)$ to $(3,3)$ without spending coins.

Move from $(3,3)$ to $(3,4)$, spending $1$ coin.

Move from $(3,4)$ to $(4,4)$, spending $1$ coin.

Cast the spell at $(4,4)$ to make $(4,5)$ yellow, spending $2$ coins.

Move from $(4,4)$ to $(4,5)$ without spending coins.

Move from $(4,5)$ to $(5,5)$, spending $1$ coin.

A total of $8$ coins are spent.

Explanation for Sample 2

The board’s colors are as shown in the table below, where blank cells are colorless.

From $( 1, 1)$ to $( 1, 2)$, spend no coins.

From $( 1, 2)$ to $( 2, 2)$, spend $1$ coin.

Cast the spell to make $( 2, 3)$ yellow, and move from $( 2, 2)$ to $( 2, 3)$, spending $2$ coins.

From $( 2, 3)$ to $( 3, 3)$, spend no coins.

From $( 3, 3)$, you can only cast the spell to reach $( 3, 2),( 2, 3),( 3, 4),( 4, 3)$.

From none of these four cells can you reach $( 5, 5)$, so it is impossible to reach the destination, and the output is $-1$.

Constraints

For $30\%$ of the testdata, $1 ≤ m ≤ 5, 1 ≤ n ≤ 10$.

For $60\%$ of the testdata, $1 ≤ m ≤ 20, 1 ≤ n ≤ 200$.

For $100\%$ of the testdata, $1 ≤ m ≤ 100, 1 ≤ n ≤ 1,000, 0 ≤ c ≤ 2$.

Translated by ChatGPT 5