题目背景

NOIP 2017 普及组第三题。

题目描述

有一个 $m\times m$ 的棋盘。每个格子原本是红色、黄色或无色。你要从左上角 $(1,1)$ 出发，到达右下角 $(m,m)$。

每一步只能走到上、下、左、右四个方向上相邻的格子，且你当前站立的格子必须有颜色。如果出发格与到达格颜色相同，这一步不花金币；颜色不同时，这一步花费 $1$ 枚金币。

你还可以使用魔法。移动前，花费 $2$ 枚金币，把下一个无色格暂时变成你选定的颜色，然后按照通常的颜色规则支付这一步的移动费用。在这个临时染色的格子上，不能再次使用魔法。必须先走到一个原本就有颜色的格子，才可以再次施法。一旦离开临时染色的格子，它便恢复无色。

求从左上角走到右下角最少需要花费的金币数。

输入格式

第一行给出两个正整数 $m,n$，分别是棋盘的边长和原本有颜色的格子数。

随后 $n$ 行，每行给出三个整数 $x,y,c$，说明格子 $(x,y)$ 的初始颜色。$c=0$ 表示红色，$c=1$ 表示黄色。每行相邻的数以一个空格隔开。

左上角坐标为 $(1,1)$，右下角为 $(m,m)$。未在输入中列出的格子均无色。保证起点 $(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

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

-1

说明/提示

样例 1

图中行、列均从 $1$ 开始编号。以下路线共用 $8$ 枚金币。

样例 2

从 $(1,1)$ 走到 $(1,2)$ 不花金币，再向下走到 $(2,2)$ 花 $1$ 枚金币。施法把 $(2,3)$ 染成黄色并走过去，共花 $2$ 枚金币。从那里走到原本为黄色的 $(3,3)$ 不再产生费用。

$(3,3)$ 的四个邻格 $(3,2)$、$(2,3)$、$(3,4)$、$(4,3)$ 此时都是无色格，只能借助魔法进入其中一个。在临时染色的格子上不能再次施法，这四个格子也都不能直接走到 $(5,5)$。终点周围没有能与起点连通的通路，答案为 $-1$。

原题的分档数据范围如下。