#include<cstdio>
#include<cstring>
using namespace std;
const int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
int m,n;
int ans=-1,map[100+1][100+1];
bool book[100+1][100+1];
void dfs(int x,int y,int cnt,bool flag){
	if(cnt>=ans)return;
	if(x==m&&y==m){
		ans=cnt<ans||ans==-1?cnt:ans;
		return;
	}
	for(int i=0;i<4;i++){
		int tox=x+dir[i][0],toy=y+dir[i][1];
		if(1<=tox&&tox<=m&&1<=toy&&toy<=m&&!book[tox][toy]){
			book[tox][toy]=true;
			int add=0;
            bool f=false;
			if(map[x][y]!=map[tox][toy])add=1;
			if(map[tox][toy]){
                add=2;
                if(flag)continue;
                f=true;
            }
			dfs(tox,toy,cnt+add,f);
			book[tox][toy]=false;
		}
	}
}
int main(){
	memset(map,-1,sizeof(map));
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++){
		int x,y,c;
		scanf("%d%d%d",&x,&y,&c);
		map[x][y]=c;
	}
	book[1][1]=true;
	dfs(1,1,0,false);
	book[1][1]=false;
    printf("%d",ans);
	return 0;
}