#include <iostream>
using namespace std;
int sty[4]={-1,1,0,0};
int stx[4]={0,0,-1,1};//上下左右 
int a[101][101];//0为红色，1为黄色，2为无色 
int m=0,n=0; 
int f[101][101];//f为到达xx,yy时所要的金币
int wz[101][101];//纪录xx,yy是否走过 
int jb=0,d=0,xx,yy; //m2纪录是否使用过魔法 
void searchx(int x,int y,int m2,int mcd)
{
	if(m2==1)
	{
		if(mcd==false) mcd++;
		else 
		{
			m2=0; mcd=0;
		}
	}//魔法冷却计时器 
	if(xx==m&&yy==m)
    {
        wz[m][m]=1;
		return ;
    }
	for(int i=0;i<4;i++)
	{
	    int jb=0;
		xx=x+stx[i];
	    yy=y+sty[i];
		if(xx>0&&xx<=m&&yy>0&&yy<=m&&wz[xx][yy]==0)
		{    
		    /*if(a[xx][yy]!=2)
	        {
    		    m2=0;
    	    }*/
	        if(a[xx][yy]==0 || a[xx][yy]==1) //判断格子是否颜色相同并加钱 
			{
			    if(a[xx][yy]!=a[x][y])
				{
				    jb=1;
				    if(f[x][y]+jb<=f[xx][yy] || f[xx][yy]!=-1)//判断到达xx,yy点的最小金币数，进入下一层 
	    	        {
					    wz[xx][yy]=1;
						f[xx][yy]=f[x][y]+jb;
    	    		    searchx(xx,yy,m2,mcd);
    	    		    wz[xx][yy]=0;
    	    	    }
				}
				else
                {
				     if(f[x][y]+jb<=f[xx][yy] || f[xx][yy]!=-1)
					 {
                        wz[xx][yy]=1;
						f[xx][yy]=f[x][y];
    	    		    searchx(xx,yy,m2,mcd);
    	    		    wz[xx][yy]=0;
					 }
                }
			}
   	        else if(a[xx][yy]==2 && m2==0)//判断是否要使用魔法 
    	    {
	    	    if(f[x][y]+jb < f[xx][yy] || f[xx][yy]!=-1)//同上 
	    	    {   
				    jb=2;
	    	        m2=1;
				    wz[xx][yy]=1;
					a[xx][yy]=a[x][y];
					f[xx][yy]=f[x][y]+jb;
    	    		searchx(xx,yy,m2,mcd);
    	    		a[xx][yy]=2;//回溯 
    	    		wz[xx][yy]=0;
    	    	}
	        }
		}
	}
}
int main()
{   int x,y,c;
	for(int i=1;i<=m;i++)
	{
		for(int o=1;o<=m;o++)
		{
			a[i][o]=2; wz[i][o]=0;
		}
	}//将所有的格子变为无色  
	cin>>m>>n;
	for(int i=0;i<n;i++)
	{
		cin>>x>>y>>c;
		a[x][y]=c;	
	}
	f[1][1]=0;
	searchx(1,1,0,0);
	if(wz[m][m]==0)
	{
		cout<<"-1";
	}
	else
	{
        cout<<f[m][m];
	}
	return 0;
}