2017 T3 棋盘

主知识点：搜索与图论。交叉标签：图论、最短路、深搜、剪枝。
暴力标注：不属于重点 DP 退路题。
OJ 使用标准输入与标准输出。原比赛文件名为 chess.in / chess.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 256 MiB；测试点 20；总分 100。
数据来源：公开存档数据；未逐文件对照官网下载包。

题目描述

一个 $m\times m$ 棋盘的格子可能是两种颜色之一，也可能无色。从 $(1,1)$ 到 $(m,m)$，每次可向上下左右移动一格，且所在格子必须有颜色。同色格子间移动免费，异色格子间移动花费 1 枚金币。

可以花费 2 枚金币，将下一个无色格子临时染成任意一种颜色，然后按上述颜色规则移动。魔法不能连续使用：离开临时染色格子并到达原本有色的格子后才能再次使用；离开时临时颜色消失。求到达终点所需最少金币；无法到达则输出 -1。

输入格式

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

接下来的 $n$ 行，每行三个正整数 $x, y, c$， 分别表示坐标为 $(x,y)$ 的格子有颜色 $c$。

其中 $c=1$ 代表黄色，$c=0$ 代表红色。 相邻两个数之间用一个空格隔开。 棋盘左上角的坐标为 $(1, 1)$，右下角的坐标为 $( m, m)$。

棋盘上其余的格子都是无色。保证棋盘的左上角，也就是 $(1, 1)$ 一定是有颜色的。

输出格式

一个整数，表示花费的金币的最小值，如果无法到达，输出 -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

样例 2

输入：

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

输出：

-1

数据范围与特殊性质

对于 $30\%$ 的数据，$1 ≤ m ≤ 5, 1 ≤ n ≤ 10$。

对于 $60\%$ 的数据，$1 ≤ m ≤ 20, 1 ≤ n ≤ 200$。

对于 $100\%$ 的数据，$1 ≤ m ≤ 100, 1 ≤ n ≤ 1,000, 0 ≤ c ≤ 1$。

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P3956
• 赛事：NOIP 普及组复赛（CSP-J 前身） 2017。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。