题目描述：

在一片花园中，有一个被精心布置成 mxm方格形状的神秘区域，这里的每一个方格就像是花园中的一块独特的小天地。花园的主人为了增添乐趣，在这些方格中放置了不同颜色的宝石或者什么都没放。宝石只有两种颜色，闪耀的红宝石和璀璨的黄宝石，而那些空着的方格就像是隐藏在花丛中的秘密角落，等待着被发现和改变。

你是一位受邀前来的幸运冒险者，接到了一个充满挑战的任务：

从这个神秘区域的左上角入口出发，穿越重重方格，最终抵达右下角的出口，收集这片花园中的奇妙体验。在这场冒险中，有着一些特别的规则。

首先，你每一步都必须踏在有宝石的方格上，那些空着的方格是无法直接落脚的，你每次移动只能选择向上、下、左、右这四个方向。

当你从一个放有宝石的方格移动到另一个放有宝石的方格时，如果两颗宝石颜色相同，那么你可以顺利通过，不会消耗任何体验值；但要是宝石颜色不一样，那你在跨越的过程中会收获一份独特的经验，但需要付出 1 点体验值，因为不同颜色的宝石之间的转换需要你更加小心和专注。

幸运的是，你还拥有一种神奇的花园魔法，但使用它需要消耗 2 点体验值。这个魔法可以让下一个空着的方格瞬间出现一颗你指定颜色的宝石（变成你想要的红宝石或者黄宝石），从而让你能够踏上它继续前进。然而，这个魔法不能连续使用，它需要时间来恢复魔力。一旦你使用魔法踏上了那个变出宝石的方格，魔法就会进入冷却状态，直到你离开这个方格，再次踏上原本就有宝石的方格时，魔法才会重新准备好，等待你的下一次召唤。而且当你离开那个靠魔法变出宝石的方格后，它就会恢复成空着的状态，仿佛魔法只是在这里短暂地留下了痕迹。

现在，挑战开始了！你要怎样规划自己的路线，才能从花园的左上角走到右下角，并且消耗最少的体验值呢？

输入格式：

第一行输入两个正整数m，n （m代表花园中这个神秘区域的大小，n表示宝石的数量 。

接下来的 n 行，每行有 3 个数字x, y ,z ，分别描述花园中坐标(x,y)的方格的宝石的情况：

如果z是1，代表这个方格中有一颗黄宝石。

如果z是0，表示这个方格中有一颗红宝石。

这个区域的左上角的坐标是(1,1)，右下角的坐标是(m,m)。

输出格式：

输出一个整数，这个整数就是你完成这次花园冒险从左上角走到右下角所花费的最少体验值。

如果无法走到，输出-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

提示

数据范围

对于 30%的数据, 1≤m≤5,1≤n≤10。

对于 60%的数据, 1≤m≤20,1≤n≤200。

对于 100%的数据, 1≤m≤100,1≤n≤1,000。