/*
思路分析：
1 输入 n 代表棋子的数量  m 代表棋盘的大小(m*m)
2 把地图 1 全部赋值为 -1
3 循环(1~n)输入每个棋子的信息
	1 输入棋子所在的行下标 列下标 棋子颜色
	2 把棋子颜色存入地图中
4 循环遍历金币数数组 遍历为 0x3f 
5 定义广搜函数
	1 入队
	2 循环直到队列为空
		1 标记队首元素 
		2 出队
		3 循环遍历四个方向
			1 计算出下一个位置
			2 越界判断
			3 定义临时变量 c1 表示当前点的原始颜色 c2 表示下一个点的颜色 v 初始化为当前点的花费
			4 分情况讨论
				1 当前原始有 下一个有
					1 判断 c1 和 c2 是否不同
					2 下一个点的花费+1
					3 判断下一个点的花费 和 花费数组中 下一个点的值的大小
						1 如果下一个点的花费小的时候入队
						2 更新花费数组中下一个点的值
				2 当前原始有 下一个无
					1 下一个点的花费+2
					2 判断下一个点的花费 和 花费数组中 下一个点的值的大小
						1 如果下一个点的花费小的时候入队
						2 更新花费数组中下一个点的值
				3 当前原始无 下一个有 
					1 判断 c1 和 c2 是否不同
					2 下一个点的花费+1
					3 判断下一个点的花费 和 花费数组中 下一个点的值的大小
						1 如果下一个点的花费小的时候入队
						2 更新花费数组中下一个点的值
6 广搜()
7 如果终点为 0x3f3f3f3f 输出-1
8 否则 输出金币数 
*/
#include <bits/stdc++.h>
using namespace std;
struct node
{
	int x,y,s,coin;
}t,u;
queue <node> q;
int n,m;
int cost[105][105];
int mapp[105][105];
int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
void bfs()
{
	q.push({1,1,mapp[1][1],0});
	while(!q.empty())
	{
		t=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int nx=t.x+d[i][0];
			int ny=t.y+d[i][1];
			int c1=mapp[t.x][t.y],c2=mapp[nx][ny],v=t.coin;
			if(c1!=-1 && c2!=-1)
			{
				if(c1!=c2) v++;
				if(v<cost[nx][ny])
				{
					cost[nx][ny]=v;
					q.push({nx,ny,c2,v});
				}
			}
			else if(c1!=-1 && c2==-1)
			{
				v+=2;
				if(v<cost[nx][ny])
				{
					cost[nx][ny]=v;
					q.push({nx,ny,c1,v});
				}
			}
			else if(c1==-1 && c2!=-1)
			{
				if(c1!=c2) v++;
				if(v<cost[nx][ny])
				{
					cost[nx][ny]=v;
					q.push({nx,ny,c2,v});
				}
			}
		}
	}
}
int main()
{
	memset(mapp,-1,sizeof(mapp));
	memset(cost,0x3f,sizeof(cost));
	cost[1][1]=0;
	cin >> m >> n;
	while(n--)
	{
		int xx,yy,a;
		cin >> xx >> yy >> a;
		mapp[xx][yy]=a;
	}
	bfs();
	if(cost[m][m]==0x3f3f3f3f)
	{
		cout << -1;	
		return 0;
	}
	cout << cost[m][m];
	return 0;
}