#include<bits/stdc++.h>
using namespace std;
#define int long long
int s[110][1010];
int nu[110][1010];
int vis[110][1010];
int n,m;
int ans=1e18l;
int hh=1e18l;
int dr[4]={-1,0,1,0};
int dc[4]={0,1,0,-1};
int puanduan(int w,int p)
{
	if(w<1||w>m||p<1||p>m||vis[w][p]==1)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}
void dfs(int row,int col,int sum,int color,int flag)
{
	if(row==m&&col==m)
	{
		ans=min(ans,sum);
		//cout<<sum<<endl;
		return;
	}
	if(sum>=ans) return;
	for(int i=0;i<4;i++)
	{
		int r=dr[i]+row;
		int c=dc[i]+col;
		if(puanduan(r,c)==1)
		{
			vis[r][c]=1;
			if(s[r][c]!=color&&s[r][c]!=-1) 
			{
				dfs(r,c,sum+1,s[r][c],flag);
			}
			else if(s[r][c]!=color&&s[r][c]==-1&&flag==0)
			{
				dfs(r,c,sum+2,color,1);
			}
			else if(s[r][c]!=color&&s[r][c]==-1&&flag!=0)
			{
				return;
			}
			else
			{
				dfs(r,c,sum,color,0);
			}
			vis[r][c]=0;
		}
	}
}
signed main()
{
	//freopen("chess.in","r",stdin);
	//freopen("chess.out","w",stdout);
	cin>>m>>n;
	memset(s,-1,sizeof(s));
	for(int i=1;i<=n;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		s[x][y]=z;
	}
	nu[1][1]=0;
	dfs(1,1,0,s[1][1],0);
	if(ans==1e18l) cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}