#include<bits/stdc++.h>
using namespace std;
int n,m,s[1001][1001],b[1001][1001],ans=100000,x,y,a;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y,int ss,int f,int ff)//x、y是现在的坐标，ss是现在花费的金币数，f是现在的颜色，ff是是否使用过魔法 
{
	if(ss>=ans) return ;
	if(x==n && y==n)
	{
		ans=ss;
		return ;
	}
	for(int i=0;i<4;i++)
	{
		int xx=dx[i]+x;
		int yy=dy[i]+y;//xx、yy是下一步的坐标 
		if(b[xx][yy]==0 && xx>0 && yy>0 && xx<=n && yy<=n)
		{
			b[xx][yy]=1;
			if(s[xx][yy]==f)//如果同色（f不可能为0） 
				dfs(xx,yy,ss,f,0);
			else if(s[xx][yy]!=f && s[xx][yy]!=0)//如果不同且有色 
				dfs(xx,yy,ss+1,s[xx][yy],0);
			else if(s[xx][yy]==0 && ff==0)//如果无色 
			{
					dfs(xx,yy,ss+2,f,1);
			}
			b[xx][yy]=0;
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&a);
		s[x][y]=a+1;//无色是0，红色是1，黄色是2 
	}
	b[1][1]=1;
	dfs(1,1,0,s[1][1],0);
	if(ans==100000) ans=-1;
	printf("%d",ans);
	return 0;
}