#include<iostream> 
    #include<cstdio> 
    using namespace std; 
    int x[6]={-1,1,0,0},y[6]={0,0,-1,1}; 
    int f[1000][1000]; 
    int a,b,c,ans=99999999; 
    int m,n; 
    int color[1000][1000]={-1};
    void dfs(int x1,int y1,int col,int z,int M) 
    { 
    	int tx,ty; 
    	if(x1==m&&y1==m) 
    	{ 
    		if(M<ans) ans=M; 
    	} 
    	else 
    	{ 
    		for(int r=0;r<4;r++) 
    		{ 
    			tx=x1+x[r];
    			ty=y1+y[r];
    			if((tx>=1&&tx<=m)&&(ty>=1&&ty<=m)&&(f[tx][ty]>M))
    				{ 
    					if(color[tx][ty]>=0)
    						{ 
    							if(color[tx][ty]==col)
    								{
    									f[tx][ty]=M; dfs(tx,ty,col,0,M); 
    								} 
    							else 
    							{
    								f[tx][ty]=M+1;
    								dfs(tx,ty,(col+1)%2,0,M+1); 
    							} 
    						} 
    					else 
    					{
    						if(z==0&&f[tx][ty]>M+2) 
    						{
    							f[tx][ty]=M+2; dfs(tx,ty,col,1,M+2); 
    						} 
    					} 
    			} 
    		} 
    	} 
    } 
    int h2872()
    { 
    	freopen("checkerboard.in","r",stdin); 
    	freopen("checkerboard.out","w",stdout);
    	cin>>m>>n; 
    	for(int i=1;i<=m;i++) 
    		for(int j=1;j<=m;j++)
    			{
    				color[i][j]=-1; f[i][j]=999999; 
    			} 
    	for(int i=1;i<=n;i++) 
    	{
    		cin>>a>>b>>c; color[a][b]=c; 
    	} 
    	dfs(1,1,color[1][1],0,0); 
    	if(ans==99999999) 
    		cout<<-1; 
    	else cout<<ans;
    	return 0; 
    }
    int huhu=h2872();
    int main(){;}