#include<bits/stdc++.h>
using namespace std;
int m;
int dx[8]={1,0,-1,0},dy[8]={0,1,0,-1},ans=0x7fffffff;
int Map[101][101];//-1代表无色1代表黄色，0代表红色 
int vis[101][101];
void dfs(int x,int y,int cnt)//x和y统计坐标，cnt统计最优解 
{
	if(x>m||x<1||y>m||y<1)return;//超出边界剪枝 
	if(cnt>=ans)//最优性剪枝 
	return;
	if(x==m&&y==m)
	{
		if(cnt<ans)
		{
			ans=cnt;
			return;
		}
	}
	for(int i=0;i<4;i++)
	{
		int x1=x+dx[i];
		int y1=y+dy[i];
		if(Map[x1][y1]>=0&&!vis[x1][y1])//这个点是有颜色的
		{
			if(Map[x][y]==Map[x1][y1])//他与下一个格子颜色一样 
			{
				vis[x1][y1]=1;
				dfs(x1,y1,cnt);
				vis[x1][y1]=0;
			}
			else
			{
				vis[x1][y1]=1;
				dfs(x1,y1,cnt+1);
				vis[x1][y1]=0;
			}
		}
		else if(!vis[x1][y1])//无色则考虑用魔法 
		{
			vis[x1][y1]=1;
			Map[x1][y1]=Map[x][y]; 
			dfs(x1,y1,cnt+2);//加上两个金币
			Map[x1][y1]=-1;
			vis[x1][y1]=0;
		}
	}
}
int main()
{
	int n,x,y,c;
	cin>>m>>n;
	memset(Map,-1,sizeof(Map));
	for(int i=1;i<=n;i++)
	{
		cin>>x>>y>>c;
		Map[x][y]=c;//初始化 
	}
	dfs(1,1,0);
	if(ans!=0x7fffffff) 
	cout<<ans<<"\n";
	else
	cout<<-1;
}