有一个m x m的棋盘，棋盘上每一个格子可能是红色、黄色、或者没有颜色。
你需要从左上角走到右下角，但是无论何时都要处于有颜色的棋盘。并且每次移动只能移动到相邻的位置（左上右下四个方向）。当你走向的格子与当前格子颜色相同，你不需要花费金币，如果不同则需要花费1个金币。
另外，你可以花费两个金币让走向的无色的格子暂时变为你指定的颜色。但这个魔法不能连续使用，且只能持续一次移动。也就是说，当你使用这个魔法走到这个格子上，你暂时不能使用这个魔法，只有当你离开后走到一个本就拥有颜色的格子上时2你才能继续使用这个魔法，而此时被施法的格子也会重新变回无色。
现在你需要从这个魔法棋盘的左上角走到右下角，求花费的最少金币是多少？

第一行两个正整数m，n，以空格分开，分别代表棋盘大小和棋盘上有颜色的格子的数量。
接下来n行，每行三个正整数x，y，z，分别表示坐标为（x，y）的格子有颜色c。
其中c=1代表黄色，c=0代表红色，相邻两个数之间用一个空格隔开。棋盘上左上角坐标为（1，1），右下角坐标为（m，m）.
魔法棋盘上其余的格子都是无色的，且保证左上角的格子一定是有颜色的。

一个整数，表示花费的金币的最小值。若无法到达，输出-1。

1<=m<=100
1<=n<=1000

计算机学院2023级ACM集训队选拔赛（4）