#include<bits/stdc++.h>
using namespace std;
int m,n;
int ans=0x7fffffff;
bool flag;
//
int dis[201][201];
bool vis[201][201];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
//
void dfs(int x,int y,int s)
{
	if(x==m&&y==m)
	{
		flag=1;
		ans=min(s,ans);
		return;
	}
	if(s>=ans) return;
	for(int k=0;k<4;k++)
	{
		int nx=x+dx[k],ny=y+dy[k];
		if(nx>=1&&nx<=m&&ny>=1&&ny<=n&&!vis[nx][ny])
		{
			vis[x][y]=1;
			//
			if(dis[nx][ny]!=0&&dis[nx][ny]==dis[x][y]) dfs(nx,ny,s); else
			if(dis[nx][ny]!=0&&dis[x][y]!=0) dfs(nx,ny,s+1); else
			if(dis[x][y]+dis[nx][ny]>=1)dis[nx][ny]=dis[x][y],dfs(nx,ny,s+2),dis[nx][ny]=0;
			//
			vis[x][y]=0;
		}
	}
}
int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++)
	{
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		dis[x][y]=c+1;
	}
	dfs(1,1,0);
	if(!flag) printf("-1"); else printf("%d",ans);
	return 0;
}