题目描述

有一个 $m\times m$ 的棋盘，部分格子为红色或黄色，其余没有颜色。从 $(1,1)$ 走到 $(m,m)$，每步只能上下左右移动。走到同色格子不花费金币，走到异色格子花费 $1$ 枚金币。

可以花费 $2$ 枚金币施展魔法，把下一步要走入的无色格子临时染成任选颜色，再按颜色是否改变支付移动费用。离开临时染色格子后，它恢复无色。不能连续施展魔法，即站在临时染色格子上时，下一步只能走到原本就有颜色的格子。起点原本有颜色。求最少花费。

输入格式

第一行两个整数 $m,n$，分别是棋盘边长和有颜色的格子数。接下来 $n$ 行，每行三个整数 $x,y,c$：坐标为 $(x,y)$，$c=0$ 表示红色，$c=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

数据范围

对于 $30\%$ 的数据，$m\le5,n\le10$；对于 $60\%$ 的数据，$m\le20,n\le200$；对于 $100\%$ 的数据，$1\le m\le100$，$1\le n\le\min(m^2,1000)$。坐标合法且不重复，$(1,1)$ 有颜色。