#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
	int x,y;
}a[10005];
int b[105][105],vis[105][105],mp[105][105];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int ans=0x3f3f3f3f;
void dfs(int k)
{
	int sum=0;
	int p=mp[a[1].x][a[1].y];
	for(int i=2;i<=k-1;i++){
		int x=a[i].x;
		int y=a[i].y;
		if(mp[x][y]==-1) sum+=2;
		else if(mp[x][y]!=p) sum+=1,p=mp[x][y];
	}
	int bx=a[k-1].x;
	int by=a[k-1].y;
	if(sum>=b[bx][by]) return ;
	b[bx][by]=sum;
	if(bx==m && by==m){
		ans=min(ans,sum);
		return ;
	}
	for(int i=0;i<4;i++){
		int nx=bx+dx[i];
		int ny=by+dy[i];
		if(nx<1 || nx>m || ny<1 || ny>m) continue;
		if(vis[nx][ny]==1) continue;
		if(mp[bx][by]==-1 && mp[nx][ny]==-1) continue;
		vis[nx][ny]=1;
		a[k].x=nx;
		a[k].y=ny;
		dfs(k+1);
		vis[nx][ny]=0;
		a[k].x=0;
		a[k].y=0;
	}
}
int main()
{
	memset(mp,-1,sizeof(mp));
	memset(b,0x3f,sizeof(b));
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int x,y,t;
		cin>>x>>y>>t;
		mp[x][y]=t;
	}
	a[1].x=1;
	a[1].y=1;
	mp[1][1]=1;
	dfs(2);
	if(ans==0x3f3f3f3f)
		cout<<-1<<endl;
	else 
		cout<<ans<<endl;
	return 0;
}

dfs深搜