#767. 棋盘

棋盘

题目描述

有一个m×m\red{m \times m}的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。

任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的), 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时,如果两个格子的颜色相同,那你不需要花费金币;如果不同,则你需要花费 1\red{1} 个金币。

另外, 你可以花费 2\red{2} 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用, 而且这个魔法的持续时间很短,也就是说,如果你使用了这个魔法,走到了这个暂时有颜色的格子上,你就不能继续使用魔法; 只有当你离开这个位置,走到一个本来就有颜色的格子上的时候,你才能继续使用这个魔法,而当你离开了这个位置(施展魔法使得变为有颜色的格子)时,这个格子恢复为无色。

现在你要从棋盘的最左上角,走到棋盘的最右下角,求花费的最少金币是多少?

输入格式

数据的第一行包含两个正整数 m\red{m}n\red{n},以一个空格分开,分别代表棋盘的大小,棋盘上有颜色的格子的数量。

接下来的 n\red{n} 行,每行三个正整数 x\red{x}y\red{y}c\red{c}, 分别表示坐标为xy\red{(x, y)}的格子有颜色 c\red{c}。 其中 c=1\red{c=1 }代表黄色,c=0\red{ c=0} 代表红色。 相邻两个数之间用一个空格隔开。 棋盘左上角的坐标为1,1\red{( 1, 1)},右下角的坐标为m,m\red{( m, m)}

棋盘上其余的格子都是无色。保证棋盘的左上角,也就是11\red{( 1, 1)} 一定是有颜色的。

输出格式

输出一行,一个整数,表示花费的金币的最小值,如果无法到达,输出1\red{-1}

样例

样例输入1

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

样例输出1

8

样例解释1

img

11\red{(1,1)}开始,走到(12\red{1,2)}不花费金币

12\red{(1,2)}向下走到22\red{(2,2)}花费 1\red{1 }枚金币

22\red{(2,2)}施展魔法,将23\red{(2,3)}变为黄色,花费2\red{ 2 }枚金币

22\red{(2,2)}走到23\red{(2,3)}不花费金币

23\red{(2,3)}走到33\red{(3,3)}不花费金币

33\red{(3,3)}走到34\red{(3,4)}花费1\red{ 1 }枚金币

34\red{(3,4)}走到44\red{(4,4)}花费 1\red{1 }枚金币 从44\red{(4,4)}施展魔法,将45\red{(4,5)}变为黄色,花费 2枚金币,\red{2 枚金币,}

44\red{(4,4)}走到45\red{(4,5)}不花费金币

45\red{(4,5)}走到55\red{(5,5)}花费 1\red{1 }枚金币

共花费 8 }$枚金币。

样例解释2

img

11\red{(1,1)}走到12\red{(1,2)},不花费金币

12\red{(1,2)}走到22\red{(2,2)},花费 1\red{1 }金币

施展魔法将23\red{(2,3)}变为黄色,并从22\red{(2,2)}走到23\red{(2,3)}花费 2\red{2} 金币

23\red{(2,3)}走到33\red{(3,3)}不花费金币

33\red{(3,3)}只能施展魔法到达32),(23),(34),(43\red{(3,2),( 2,3),( 3,4),(4,3)} 而从以上四点均无法到达55\red{(5,5)},故无法到达终点,输出1\red{-1}

提示

对于30%\red{ 30\%}的数据, 1m5\red{1 \le m \le 5}1n10\red{1 \le n \le 10}

对于60%\red{ 60\%}的数据, 1m20\red{1 \le m \le 20}1n200\red{1 \le n \le 200}

对于 100%\red{100\%}的数据, 1m100\red{1 \le m \le 100}1n1,000\red{1 \le n \le 1,000}