棋盘

题目描述

有一个 m×m 的棋盘，棋盘上每个格子可能是红色（用 0 表示）、黄色（用 1 表示）或无色。你可以从上、下、左、右四个方向前进，需要从棋盘左上角 (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

数据范围

• 1 ≤ m ≤ 100
• 1 ≤ n ≤ 1000
• 0 ≤ c ≤ 1
• 1 ≤ x, y ≤ m
• 起点 (1,1) 保证有颜色

本题为 NOIP 2017 普及组第 3 题（洛谷 P3956），题面规则与原题一致。