该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

信号维修

题目背景

某通信基地由一个 $m \times m$ 的区域组成。部分区域已经部署了信号中继器，中继器的工作频段只有两种：频段 $0$ 和频段 $1$；其余区域尚未部署中继器。

维修员需要从基地左上角的起始站前往右下角的主控站。维修员只能停留在存在信号的区域中，但可以临时激活一个尚未部署中继器的区域。

不同频段之间切换会产生额外代价，请你计算到达主控站的最小总代价。

题目描述

基地可以看作一个 $m\times m$ 的方格图，左上角坐标为 $(1,1)$，右下角坐标为 $(m,m)$。

每个格子可能具有频段 $0$、频段 $1$，或没有任何信号。维修员从 $(1,1)$ 出发，每次可以向上下左右四个方向移动一格。

维修员不能停留在没有信号的格子上。

若维修员从一个有信号的格子移动到相邻的另一个有信号格子：

• 两个格子的频段相同，代价为 0；
• 两个格子的频段不同，代价为 1。

此外，维修员可以在当前格子的相邻无信号格子上临时建立中继器，并指定该临时中继器使用频段 0 或频段 1。建立临时中继器的代价为 2。

临时中继器只能供维修员进入一次：当维修员离开该格子后，该格子立即恢复为无信号状态。

需要特别注意的是，维修员不能连续建立临时中继器。也就是说，若维修员当前位于一个由临时中继器提供信号的格子，则下一步必须移动到原本就有信号的格子；不能直接在相邻无信号格子上再次建立临时中继器。

求维修员从 $(1,1)$ 到达 $(m,m)$ 的最小代价。若无法到达，则输出 $-1$。

输入格式

第一行包含两个正整数 $m,n$，分别表示基地边长与已部署中继器的格子数量。

接下来 $n$ 行，每行包含三个整数 $x,y,c$，表示坐标 $(x,y)$ 处部署了一个频段为 $c$ 的中继器。

其中：

• $c=0$ 表示频段 $0$；
• $c=1$ 表示频段 $1$。

未在输入中给出的格子均没有信号。保证 $(1,1)$ 处一定存在中继器。

输出格式

输出一个整数，表示从起始站到主控站的最小代价。若无法到达主控站，输出 $-1$。

数据范围与约定

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

对于 60% 的数据，$1\le m\le20,\ 1\le n\le200$。

对于 100% 的数据，$1\le m\le100,\ 1\le n\le1000,\ 0\le c\le1$。

样例输入 1

5 7
1 1 0
1 2 0
2 2 1
3 3 1
3 4 0
4 4 1
5 5 0

样例输出 1

8

样例输入 2

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

样例输出 2

-1