#include<cstdio>
#include<algorithm>
using namespace std;
const int M = 233;
const int MAX = 0x3f3f3f3f;
bool v[M][M], flag = 0;
int m, n, f = 0, r = 0, cnt = 0, dx[6] = {-1, 0, 0, 1}, dy[6] = {0, 1, -1, 0};
struct G {
	int money = MAX;
	int c1 = 0, c2 = 0;//c1表示原色，c2表示现在的颜色
	bool magic = 0;
} g[M][M];
struct Q {
	int x, y;
} q[M * M];
int main(void) {
	scanf("%d%d", &m, &n);
	for (int i = 1; i <= n; ++i) {
		int tt1, tt2, co;
		scanf("%d%d%d", &tt1, &tt2, &co);
		g[tt1][tt2].c1 = g[tt1][tt2].c2 = co + 1; //方便判断颜色
	}
	g[1][1].money = 0, q[r + 1].x = q[r + 1].y = 1, ++r, ++cnt, v[1][1] = 1; //首元素入队
	while (cnt > 0) {
		int X = q[f + 1].x, Y = q[f + 1].y;//出队
		++f, --cnt;
		for (int i = 0; i < 4; ++i) {//四个方向
			int tx = X + dx[i], ty = Y + dy[i];
			if (tx >= 1 && tx <= m && ty >= 1 && ty <= m && (g[X][Y].c1 == 0 && g[tx][ty].c1 == 0) == 0) { //未越界且不都是白色
				if (v[tx][ty] == 0) q[r + 1].x = tx, q[r + 1].y = ty, ++r, v[tx][ty] = 1, ++cnt; //未拜访则入队
				if (g[tx][ty].c1 == 0) { //下一个点是白色
					g[tx][ty].magic = 1; //用魔法
					if (g[X][Y].money + 2 < g[tx][ty].money) { //施展魔法，花两块钱
						g[tx][ty].money = g[X][Y].money + 2;
						g[tx][ty].c2 = g[X][Y].c2;//贪心策略：更新为上一个点的颜色，总是最优解
					}
				} else {//下一个点是彩色
					if (g[X][Y].c2 == g[tx][ty].c2) g[tx][ty].money = min(g[X][Y].money, g[tx][ty].money); //颜色相同，不花钱
					else g[tx][ty].money = min(g[X][Y].money + 1, g[tx][ty].money);//颜色不同，花一块钱
				}
				if (tx == m && ty == m) {//找到了
					flag = 1;
					break;
				}
			}
		}
		if (g[X][Y].magic == 1) g[X][Y].magic = g[X][Y].c2 = 0; //离开这个点，去除魔法 
		if (flag == 1) break; 
	}
	printf("%d", g[m][m].money == MAX ? -1 : g[m][m].money);
	return 0;
}