题目描述

有一个 $m \times m$ 的棋盘，每个格子可能是红色、黄色或无色。从棋盘左上角 $(1,1)$ 走到右下角 $(m,m)$，规则如下：

• 只能站在有颜色的格子上（起点一定有颜色）
• 每次可以向上、下、左、右移动
• 同色格子间移动不花费金币
• 不同颜色格子间移动花费 $1$ 个金币
• 可以花费 $2$ 个金币施展魔法，将下一个无色格子暂时变为指定颜色
• 魔法不能连续使用，必须走到有颜色的格子后才能再次使用
• 离开魔法变色的格子后，该格子恢复无色

求从左上角到右下角花费的最少金币数，如果无法到达输出 $-1$。

输入格式

第一行两个整数 $m, n$，表示棋盘大小和有颜色格子的数量。

接下来 $n$ 行，每行三个整数 $x, y, c$，表示坐标 $(x,y)$ 的格子颜色为 $c$（$0$ 表示红色，$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

8

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

-1

提示

样例 1 说明

从 $(1,1)$ 开始，走到 $(1,2)$ 不花费金币
从 $(1,2)$ 向下走到 $(2,2)$ 花费 $1$ 枚金币
从 $(2,2)$ 施展魔法，将 $(2,3)$ 变为黄色，花费 $2$ 枚金币
从 $(2,2)$ 走到 $(2,3)$ 不花费金币
从 $(2,3)$ 走到 $(3,3)$ 不花费金币
从 $(3,3)$ 走到 $(3,4)$ 花费 $1$ 枚金币
从 $(3,4)$ 走到 $(4,4)$ 花费 $1$ 枚金币
从 $(4,4)$ 施展魔法，将 $(4,5)$ 变为黄色，花费 $2$ 枚金币
从 $(4,4)$ 走到 $(4,5)$ 不花费金币
从 $(4,5)$ 走到 $(5,5)$ 花费 $1$ 枚金币
共花费 $8$ 枚金币。

样例 2 说明

从 $(1,1)$ 走到 $(1,2)$ 不花费金币
从 $(1,2)$ 走到 $(2,2)$ 花费 $1$ 金币
施展魔法将 $(2,3)$ 变为黄色，从 $(2,2)$ 走到 $(2,3)$ 花费 $2$ 金币
从 $(2,3)$ 走到 $(3,3)$ 不花费金币
从 $(3,3)$ 只能施展魔法到达 $(3,2),(2,3),(3,4),(4,3)$，但这些点都无法到达 $(5,5)$，故无法到达终点。

数据规模与约定

对于全部的测试点，保证 $1 \leq m \leq 100$，$1 \leq n \leq 1000$，起点 $(1,1)$ 一定有颜色。

本题改编自 NOIP 2017 普及组 T3