#include<bits/stdc++.h>
using namespace std;
int n,m,a[100][100],vis[100][100],x,y,z,ans=1000000;
//
//   1 2 3 4 5
//1  0 0 
//2    1
//3      1 0
//4        1
//5          0
//
//从(1,1)开始，走到(1,2)不花费金币
//从(1,2)向下走到(2,2)花费1枚金币
//从(2,2)施展魔法，将(2,3)变为黄色，花费2枚金币
//从(2,2)走到(2,3)不花费金币
//从(2,3)走到(3,3)不花费金币
//从(3,3)走到(3,4)花费1枚金币
//从(3,4)走到(4,4)花费1枚金币
//从(4,4)施展魔法，将(4,5)变为黄色，花费2枚金币，
//从(4,4)走到(4,5)不花费金币
//从(4,5)走到(5,5)花费1枚金币
//共花费8枚金币。
int fx[4]={-1,1,0,0};
int fy[4]={0,0,1,-1};
void dfs(int x,int y,int sum,bool magic){

	if(x==n&&y==n){
		ans=min(ans,sum);
		return;
	} 
	for(int i=0;i<=3;i++){
		int tx=x+fx[i];
		int ty=y+fy[i]; 
		
		if(tx>=1&&tx<=n&&ty>=1&&ty<=n&&vis[tx][ty]==0){
			//cout<<x<<" "<<y<<" "<<sum<<" "<<tx<<" "<<ty<<endl;
			if(a[tx][ty]==-1){
				if(magic==false) {
					vis[tx][ty]=1;
					a[tx][ty]=a[x][y];
					dfs(tx,ty,sum+2,true);
					a[tx][ty]=-1;
					vis[tx][ty]=0;
				}
			} 
			else{
				vis[tx][ty]=1;
				if(a[x][y]==a[tx][ty])	dfs(tx,ty,sum,false);
				else dfs(tx,ty,sum+1,false);
				vis[tx][ty]=0;
			}
		}
	}
	
	
}
int main(){
	cin>>n>>m;
	memset(a,-1,sizeof(a));
	while(m--){
		cin>>x>>y>>z;
		a[x][y]=z;
	}
	if(a[1][1]==-1){
		cout<<-1;
		return 0;
	}
	vis[1][1]=1;
	dfs(1,1,0,false);
	if(ans==1000000) cout<<-1;
	else	cout<<ans;
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++) cout<<setw(4)<<a[i][j];
//		cout<<endl; 
//	}
	
	

	return 0;
}

/**************************************************************
	Problem: 1483
	User: hulaoshi
	Language: C++
	Result: Time Limit Exceed
****************************************************************/