#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;
}