#include <bits/stdc++.h>
using namespace std;
int m,n,c,a[105][105]={0},x,y,ans=INT_MAX;
int dx[]={-1,0,1,0},dy[]={0,-1,1,0};
void dfs(int x,int y,int sum,int f){
	if(x<1||y<1||x>m||y>m)return;
	if(a[x][y]==0)return;
	if(x==m&&y==m){
		if(sum<ans)ans=sum;
		return;
	}
	for(int i=0;i<4;++i){
		int xx=x+dx[i],yy=y+dy[i];
		if(a[xx][yy]!=0){
			if(a[xx][yy]==a[x][y]){
				dfs(xx,yy,sum,0);
			}
			else dfs(xx,yy,sum+1,0);
		}
		else if(!f){
			a[xx][yy]=a[x][y];
			dfs(xx,yy,sum+2,1);
			a[xx][yy]=0;
		}
//		cout<<xx<<' '<<yy<<' '<<x<<' '<<y<<' '<<sum<<' '<<ans<<endl;
	}
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;++i){
		cin>>x>>y>>c;
		a[x][y]=c+1;
	}
	if(ans==INT_MAX)cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}