#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int n,m,n2;int a[N];
int d[5];
vector<pair<int,int> >G[N];
void jianbian(int u,int v)
{
	if(a[u]==a[v]&&a[v]!=-1) G[u].push_back(make_pair(v,0));
	if(a[u]!=-1&&a[v]==-1)
	{
		for(int i=0;i<4;i++)
		{
			int v1=v+d[i];
			if(v1==u) continue;
			if(v1<1||v1>n2) continue;
			if(a[v1]==-1) continue;
			if(a[u]!=a[v1]) G[u].push_back(make_pair(v1,3));
			else G[u].push_back(make_pair(v1,2));
		}
	}
	if(a[u]!=-1&&a[v]!=-1&&a[u]!=-1) G[u].push_back(make_pair(v,1));
}
priority_queue<pair<int,int> >q;
int dd[N];bool vis[N];
void dj()
{
	q.push(make_pair(0,1));
	dd[1]=0;
	while(q.size())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=0;i<G[u].size();i++)
		{
			int v=G[u][i].first,w=G[u][i].second;
			if(dd[v]>dd[u]+w)
			{
				dd[v]=dd[u]+w;
				q.push(make_pair(-dd[v],v));
			}
		}
	}
}
int main()
{
//	freopen("P3956_9.in","r",stdin);
	cin>>m>>n;d[0]=-1,d[1]=1,d[2]=m,d[3]=-m;
	memset(a,-1,sizeof(a));
	for(int i=1;i<=n;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		int v=(x-1)*m+y;
		a[v]=w;
	}
	n2=m*m;
	for(int i=1;i<=n2;i++)
	{
		int v1=i+1;
		if(1<=v1&&v1<=n2) jianbian(i,v1);
		v1=i-1;
		if(1<=v1&&v1<=n2) jianbian(i,v1);
		v1=i-m;
		if(1<=v1&&v1<=n2) jianbian(i,v1);
		v1=i+m;
		if(1<=v1&&v1<=n2) jianbian(i,v1);
	}
//	int tot=0;
//	for(int i=1;i<=m;i++)
//	{
//		for(int j=1;j<=m;j++)
//		   cout<<a[++tot]<<" ";
//		cout<<endl;
//	}
	if(a[n2]==-1)
	{
		if(a[n2-m]!=-1) G[n2-m].push_back(make_pair(n2,2));
		if(a[n2-1]!=-1) G[n2-1].push_back(make_pair(n2,2));
	}
	memset(dd,0x3f,sizeof(dd));
	dj();
	if(dd[n2]==0x3f3f3f3f)
	{
		cout<<-1<<endl;
		return 0;
	}
	cout<<dd[n2]<<endl;
	return 0;
}