题目描述
$m \times m$ 网格上部分格子刷了颜色（黄/红），其余无色。巡线车从 $(1,1)$ 走到 $(m,m)$， 只能四向移动，且所站格子必须有颜色：
- 移入相邻有色格：同色花 $0$ 金币，异色花 $1$ 金币；
- 若相邻格无色，可花 $2$ 金币施魔法把它临时变成自己当前的颜色走过去（之后走同色 $0$、 异色 $1$）；魔法不能连续使用，离开该格后恢复无色。
$(1,1)$ 一定有颜色。求最少花费；无法到达输出 $-1$。
输入格式
第一行两个正整数 $m$ 和有颜色格数 $n$； 以下 $n$ 行，每行三个整数 $x, y, c$：坐标 $(x,y)$ 的格子颜色为 $c$（$0$ 红 $1$ 黄）。
输出格式
一行，一个整数：最少花费；无法到达为 $-1$。
数据范围
$$m \le 100,\ n \le 1000$$
，$(1,1)$ 保证有颜色。