#1AC #17AC 其他WA 10分求条 bfs

#include <bits/stdc++.h>
using namespace std;
const int N=110,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int c[N][N],vis[N][N][2],i,n,m,x,y,color;
queue <pair<pair<int,int>,int> > q;
void bfs(){
	int fx,fy,fb,i,sx,sy,ccc;
	while(!q.empty()){
		fx=q.front().first.first;fy=q.front().first.second;fb=q.front().second;q.pop();
		if(fx==m&&fy==m){cout<<vis[fx][fy][fb];exit(0);}
		for(i=0;i<4;i++){
			sx=fx+dx[i];sy=fy+dy[i];
			if(sx<1||sx>m||sy<1||sy>m) continue;
			if(c[sx][sy]>=0){
				ccc=vis[fx][fy][fb]+(c[fx][fy]==c[sx][sy]?0:1);
				if(vis[sx][sy][0]==-1||vis[sx][sy][0]>ccc)
					vis[sx][sy][0]=ccc,q.push({{sx,sy},0});
			}else if(c[sx][sy]==-2&&fb==0){
				ccc=vis[fx][fy][fb]+2;
				if(vis[sx][sy][1]==-1||vis[sx][sy][1]>ccc)
					vis[sx][sy][1]=ccc,q.push({{sx,sy},1});
			}
		}
	}
}
int main(){
	memset(c,-2,sizeof(c));memset(vis,-1,sizeof(vis));
	q.push({{1,1},0});vis[1][1][0]=0;
	cin>>m>>n;
	for(i=1;i<=n;i++) cin>>x>>y>>color,c[x][y]=color;
	bfs();
	cout<<-1;
}