#include<bits/stdc++.h>
#include<windows.h>
#define ll long long
using namespace std;
struct color {
	int color,x,y;
} a[100000];
int n,m,ma[105][105],fx,fy,ans=8177,vis[105][105],can=0;
int dx[4]= {1,-1,0,0},dy[4]= {0,0,1,-1};
void dfs(int num,int xx,int yy,int color) {
	if(xx==fx&&yy==fy) {
//		cout<<ans<<' '<<num<<'ok'<<endl;
		ans=min(ans,num);
		return;
	}
	for(int i=0; i<=3; i++) {
		int nx=xx+dx[i],ny=yy+dy[i];
//		Sleep(1000);
//		cout<<nx<<' '<<ny<<' '<<endl;
		if(!(nx<=m&&ny>=1&&ny<=m))
		if(ma[nx][ny]==ma[xx][yy]&&vis[nx][ny]==0&&nx>=1&&nx<=m&&ny>=1&&ny<=m) {
			vis[nx][ny]=1;
			color=ma[nx][ny];
			if(num>ans)
				return;
			dfs(num,nx,ny,color);
			vis[nx][ny]=0;
			color=ma[nx][ny];
		} else {
			if(ma[nx][ny]!=ma[xx][yy]&&ma[nx][ny]!=0&&vis[nx][ny]==0&&nx>=1&&nx<=m&&ny>=1&&ny<=m) {
				vis[nx][ny]=1;
				color=ma[nx][ny];
				if(num>ans)
					return;
				dfs(num+1,nx,ny,color);
				vis[nx][ny]=0;
				color=ma[nx][ny];
			} else {
				if(ma[nx][ny]!=ma[xx][yy]&&ma[nx][ny]==0&&vis[nx][ny]==0&&can==0&&nx>=1&&nx<=m&&ny>=1&&ny<=m) {
					vis[nx][ny]=1;
					color=ma[xx][yy];
					can=1-can;
					if(num>ans)
						return;
					dfs(num+2,nx,ny,color);
					vis[nx][ny]=0;
					color=ma[nx][ny];
					can=0;
				}
			}
		}
	}
}
int main() {
	memset(ma,0,sizeof(ma));
	memset(vis,0,sizeof(vis));
	cin>>m>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i].x>>a[i].y>>a[i].color;
		ma[a[i].x][a[i].y]=a[i].color+1;
	}
//	for(int i=1; i<=m; i++) {
//		for(int j=1; j<=m; j++)
//			cout<<ma[i][j]<<" ";
//		cout<<endl;
//	}

	fx=m,fy=m;
	dfs(0,1,1,ma[1][1]);
	if(ans==8177)
		cout<<'0';
	else
		cout<<ans;
	return 0;
}