#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

const int N=1010;
const int inf=0x3f3f3f3f;
priority_queue<pii,vector<pii>,greater<pii> > pq;
ll n,m,a[N][N],num[N][N],ans[N],res=0x3f3f3f3f;
vector<pii> e[N];
pii color[N];
bool vis[N],flag=false;

const int dx[12]={-1,1,0,0,-1,-1,1,1,-2,2,0,0};
const int dy[12]={0,0,-1,1,-1,1,1,-1,0,0,-2,2};

bool inb(ll x,ll y){
	return x>=1 && x<=n && y>=1 && y<=n;
}

void dijkstra(){
	memset(ans,0x3f,sizeof(ans));
	memset(vis,0,sizeof(vis));
	ans[1]=0;
	pq.push((pii){0,1});
	while(!pq.empty()){
		ll u=pq.top().second;
		pq.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(ll i=0;i<e[u].size();i++){
			ll v=e[u][i].first,w=e[u][i].second;
			if(ans[v]>ans[u]+w){
				ans[v]=ans[u]+w;
				pq.push((pii){ans[v],v});
			}
		}
	}
}

int main(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=n;j++){
			a[i][j]=2,num[i][j]=-1;
		}
	}
	for(ll i=1;i<=m;i++){
		ll x,y,c;
		cin>>x>>y>>c;
		a[x][y]=c;
        num[x][y]=i;
		color[i]={x,y};
	}
	sort(color+1,color+m+1);
    if(color[m]!=(pii){n,n}){
		flag=true;
		m++;
		a[n][n]=1;
		num[n][n]=m;
		color[m]={n,n};
    }
	for(ll i=1;i<=m;i++){
		ll x=color[i].first,y=color[i].second,ad=0;
		for(ll j=0;j<12;j++){
			if(j>=4) ad=2;
			ll nx=x+dx[j],ny=y+dy[j];
			if(inb(nx,ny) && num[nx][ny]>0 && a[nx][ny]!=2){
				if(a[nx][ny]!=a[x][y]) e[i].push_back((pii){num[nx][ny],1+ad});
				else e[i].push_back((pii){num[nx][ny],ad});
			}else if(nx==n && ny==n){
                if(a[nx][ny]!=a[x][y]) e[i].push_back((pii){num[nx][ny],1+ad});
				else e[i].push_back((pii){num[nx][ny],ad});
            }
		}
	}
    dijkstra();
	if(!flag){
		if(ans[m]>=inf) cout<<-1<<"\n";
		else cout<<ans[m]<<"\n";
		return 0;
	}else{
		a[n][n]=0;
		res=min(res,ans[m]+2);
	}
	for(int i=1;i<=m;i++){
		e[i].clear();
	}
	memset(vis,0,sizeof(vis));
	for(ll i=1;i<=m;i++){
		ll x=color[i].first,y=color[i].second,ad=0;
		for(ll j=0;j<12;j++){
			if(j>=4) ad=2;
			ll nx=x+dx[j],ny=y+dy[j];
			if(inb(nx,ny) && num[nx][ny]>0 && a[nx][ny]!=2){
				if(a[nx][ny]!=a[x][y]) e[i].push_back((pii){num[nx][ny],1+ad});
				else e[i].push_back((pii){num[nx][ny],ad});
			}else if(nx==n && ny==n){
                if(a[nx][ny]!=a[x][y]) e[i].push_back((pii){num[nx][ny],1+ad});
				else e[i].push_back((pii){num[nx][ny],ad});
            }
		}
	}
    dijkstra();
	res=min(res,ans[m]+2);
    if(abs(color[m-1].first-n) && abs(color[m-1].second-n)) cout<<-1<<"\n";
	else if(ans[m]>=inf) cout<<-1<<"\n";
	else cout<<res<<"\n";
	return 0;
}