#include<iostream>
     #include<cstring>
    #include<cstdio>
    #include<iomanip>
    #include<algorithm>
    using namespace std;
    int minm,m,n,coy,cox,co,a[1050][1050],mina[1050][1050];
    int tx[4]={1,0,-1,0},ty[4]={0,1,0,-1},xx,yy;
    void s(int x,int y,int nowm,int nowco,bool used){
    	if(x==m&&y==m) {
    		if(minm>nowm)minm=nowm;}
    	else{
    	for(int i=0;i<=3;i++)
    		{xx=x+tx[i];yy=y+ty[i];
    		if(xx>=1&&xx<=m&&yy>=1&&yy<=m){
    		if(a[xx][yy]>0){
    		if(nowco==a[xx][yy]){
    			if(nowm<mina[xx][yy]){
    		{mina[xx][yy]=nowm;
    			s(xx,yy,nowm,nowco,0);}}}
    		else{
    			if(nowm<mina[xx][yy]+1){
    				
    			mina[xx][yy]=nowm+1;
    		s(xx,yy,nowm+1,a[xx][yy],0);
    			}}}
    		else{
    		if(used==0&&nowm<mina[xx][yy]+2)
    			{
    			mina[xx][yy]=nowm+2;
    		s(xx,yy,nowm+2,nowco,1);
    			}}}}}
    }                  
    int Main(){
    	freopen("checkerboard.in","r",stdin);
    	freopen("checkerboard.out","w",stdout);
    	ios::sync_with_stdio(false);
    cin>>m>>n;
     
    	for(int i=1;i<=m;i++)
    	for(int o=1;o<=m;o++)
     
    		mina[i][o]=99999999;
    	for(int i=1;i<=n;i++){
    	cin>>cox>>coy>>co;
    	co++;
    	a[cox][coy]=co;}
    	/*for(int i=1;i<=m;i++){cout<<endl;
    	for(int o=1;o<=m;o++)
    		cout<<a[i][o]<<' ';}
    	cout<<endl;*/
    	minm=99999999;
    	mina[1][1]=0;
    	s(1,1,0,a[1][1],0);
    	if(minm==99999999) cout<<-1; 
    	else 
    	cout<<minm;
    return 0;
    }
    int cr=Main();
    int main(){;}