#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x,y,sum,color;
};
int n,m,a[105][105],dx[]={-1,1,0,0},dy[]={0,0,1,-1},ans=0x3f3f3f3f;
bool vis[105][105];
void bfs()
{
	queue<node>q;
	q.push({0,0,0,a[0][0]});
	while(q.size())
	{
		vis[q.front().x][q.front().y]=1;
		if(q.front().x==m-1&&q.front().y==m-1)ans=min(ans,q.front().sum);
		for(int i=0;i<4;i++)
		{
			int nx=q.front().x+dx[i],ny=q.front().y+dy[i];
			if(vis[nx][ny]||nx<0||nx==m|ny<0||ny==m||(a[nx][ny]==0&&a[q.front().x][q.front().y]==0))continue;
			if(a[nx][ny]==0)q.push({nx,ny,q.front().sum+2,q.front().color});
			else if(q.front().color!=a[q.front().x][q.front().y])q.push({nx,ny,q.front().sum+1,a[q.front().x][q.front().y]});
			else q.push({nx,ny,q.front().sum,q.front().color});
		}
		q.pop();
	}
}
int main()
{
//	freopen("chess.in","r",stdin);
//	freopen("chess.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	while(n--)
	{
		int i,j,k;
		cin>>i>>j>>k;
		a[i-1][j-1]=k+1; 
	}
	bfs();
	if(ans==0x3f3f3f3f)ans=-1;
	cout<<ans;
	return 0;
}

样例还没过( T _ T )