#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f
int a[110][110];
int dis[110][110];
int dx[]={0,0,-1,1,1,1,-1,-1,0,0,-2,2};
int dy[]={1,-1,0,0,1,-1,1,-1,2,-2,0,0};
int dv[]={0,0,0,0,2,2,2,2,2,2,2,2};
int m,n;

inline int read()
{
	int x=0;
	char ch=getchar();
	while(ch>57||ch<48) ch=getchar();
	while(ch>=48&&ch<=57)
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}
inline void write(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
struct node{
	int x,y,v;
	int c;
	bool operator <(const node &a)const{
		return a.v<v;
	}
};

priority_queue<node> q;
bool check(int x,int y)
{
	if(x<=0||y<=0||x>m||y>m) return 0;
	return 1;
}
int bfs()
{
	memset(dis,INF,sizeof dis);
	q.push({1,1,0,a[1][1]});
	while(!q.empty())
	{
		node cur=q.top(); q.pop();
		int nx=cur.x,ny=cur.y,nv=cur.v,nc=cur.c;
		if(dis[nx][ny]<nv) continue;
		//cout << nv << " " << nx << " " << ny << endl;
		for(int i=0;i<12;i++)
		{
			int cx=nx+dx[i],cy=ny+dy[i],cv=nv+dv[i],cc=a[cx][cy];
			if(!check(cx,cy)) continue;
			if(!cc) continue;
			if(nc!=cc) cv++;
			if(dis[cx][cy]>cv){
				dis[cx][cy]=cv;
				q.push({cx,cy,cv,cc});
			}
		}
	}
} 
signed main()
{
	m=read(); n=read();
	cin >> m >> n;
	while(n--)
	{
		int x,y,c;
		x=read();y=read();c=read();
		a[x][y]=c+1;
	}
	bfs();
	
	if(!a[m][m])
	{
		int ans=min(dis[m][m-1],dis[m-1][m])+2;
		if(ans>=INF) write(-1);
		else write(ans);
	}
	else
	{
		if(dis[m][m]>=INF) write(-1);
		else write(dis[m][m]);
	}
	return 0;
}

照着第一篇题解改了半天，变全黑了，在线求调