#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[101][101];
bool f[101][101][2];
bool s[101][101][2];
int b[101][101][2];
int dfs(int x,int y,int c,int color)
{
    
	if(x<=0||y<=0||x>n||y>n)return 10000001;
	if(s[y][x][c])return b[y][x][c];
	if(f[y][x][c])return 10000001;
	f[y][x][c]=1;
	int ans=0;
    
    if(a[y][x]==0)
    {
        if(c==1)return 10000001;
        c=1;
        ans+=2;
    }
    else{
        c=0;
        if(a[y][x]!=color)
        {
            color=a[y][x];
            ans+=1;
        }
    }
	int cnt=10000001;
	if(x==n&&y==n)return ans;
	cnt=min(cnt,dfs(x+1,y,c,color));
	cnt=min(cnt,dfs(x,y+1,c,color));
	cnt=min(cnt,dfs(x-1,y,c,color));
	cnt=min(cnt,dfs(x,y-1,c,color));
	b[y][x][c]=cnt+ans;
	f[y][x][c]=0;
	s[y][x][c]=1;
    // cout<<y<<' '<<x<<' '<<cnt+ans<<' '<<color<<endl;
	return b[y][x][c];
}
int main()
{
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
    // memset(b,00111,sizeof(b));
	int x,y,c;
	for(int i=1;i<=m;i++)
	{
		cin>>y>>x>>c;
		a[y][x]=c+1;
	}
	int ans=dfs(1,1,0,a[1][1]);
	if(ans>=10000001)cout<<-1;
	else cout<<ans;
	return 0;
}