#include<bits/stdc++.h>
#define mi(x,y,z) (nde){x,y,z} 
//#define int long long
using namespace std;
int a[110][110];
int dp[110][110][2];
int f[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
//0表示红色，1表示黄色 
/*
dp[i][j][0]表示当前格子为红色时所需最小金币，若为黄色则是inf
dp[i][j][1]同上 

if huang dp[i][j][1]=min(dp[i-1][j][0]+1,dp[i-1][j][1],dp[i][j-1][0]+1,dp[i][j-1][1])
if hong dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1]+1,dp[i][j-1][0],dp[i][j-1][1]+1)
if wuse 上面两个  
*/
struct nde{
	int x,y,z;
};

inline int read(){
	char ch(getchar());
	int f(1),x(0);
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar(); 
	} 
	return x*f;
}

int n,m;
signed main(){
	cin>>m>>n;
	for(int i=1;i<=n;++i){
		a[read()][read()]=read()+1;
	}
	memset(dp,0x3f3f,sizeof dp);
	if(a[1][1]==1) dp[1][1][0]=0;
    else dp[1][1][1]=0;
	//0为无色，1为红色，2为黄色 
	int ss;
	queue<nde>q;
	q.push(mi(1,1,0));
	
	while(!q.empty()){
		int i=q.front().x,j=q.front().y,id=q.front().z;
		q.pop();
		if(dp[i][j][0]>=0x3f3f && dp[i][j][1]>=0x3f3f) continue;
		for(int k=0;k<4;++k){
			int x=i+f[k][0],y=j+f[k][1];
            cout<<x<<' '<<y<<endl;
			if(x<1 || x>m || j<1 || j>m) continue;
            int ans1;
			if(a[x][y]==1){
				ans1=min(dp[i][j][0],dp[i][j][1]+1);
				if(ans1<dp[x][y][0]){
					dp[x][y][0]=ans1;
					q.push(mi(x,y,0));
				} 
			}
			if(a[x][y]==2){
				ans1=min(dp[i][j][1],dp[i][j][0]+1);
				if(ans1<dp[x][y][1]){
					dp[x][y][1]=ans1;
					q.push(mi(x,y,0));
				}
			}
			if(a[x][y]==0){
				if(id) continue;
				ans1=min(dp[i][j][0]+2,dp[i][j][1]+3);
				if(ans1<dp[x][y][0]){
					dp[x][y][0]=ans1;
				}
				ans1=min(dp[i][j][1]+2,dp[i][j][0]+3);
				if(ans1<dp[x][y][1]){
					dp[x][y][1]=ans1;
				}
				q.push(mi(x,y,1));
			}
		}
	}
//	
//	for(int i=1;i<=m;++i){
//		for(int j=1;j<=m;++j){
//			if(i==j && i==1) continue;
//			if(a[i][j]==1){
//				dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]);
//				dp[i][j][0]=min(dp[i][j][0],dp[i][j-1][0]);
//				dp[i][j][0]=min(dp[i][j][0],min(dp[i-1][j][1]+1,dp[i][j-1][1]+1));
//			}
//			if(a[i][j]==2){
//				dp[i][j][1]=min(dp[i][j][1],min(dp[i][j-1][1],dp[i-1][j][1]));
//				dp[i][j][1]=min(dp[i][j][1],min(dp[i-1][j][0]+1,dp[i][j-1][0]+1));
//			}
//			if(a[i][j]==0){
//				if(a[i-1][j]!=0){
//					dp[i][j][0]=min(dp[i][j][0],min(dp[i-1][j][0]+2,dp[i][j-1][0]+2));
//					dp[i][j][0]=min(dp[i][j][0],min(dp[i-1][j][1]+3,dp[i][j-1][1]+3));
//				} 
//				if(a[i][j-1]!=0){
//					dp[i][j][1]=min(dp[i][j][1],min(dp[i-1][j][1]+2,dp[i][j-1][1]+2));
//					dp[i][j][1]=min(dp[i][j][1],min(dp[i-1][j][0]+3,dp[i][j-1][0]+3));
//				}
//			}
//		}
//	}
	int ans;
	if(a[m][m]==0){
		ans=min(dp[m][m][0],dp[m][m][1]);
	}else{
		ans=dp[m][m][a[m][m]-1];
	}
	if(ans>=0x3f3f) cout<<-1<<endl;
	else cout<<ans<<endl;
	return(0-0);
}