#include<bits/stdc++.h>
using namespace std;
struct xxx
{
	int x,y,val,flag;
	bool operator < (const xxx &n)const
	{
		return val>n.val;
	}
};
priority_queue<xxx>q;
int n,m;
int g[105][105],vis[105][105];
void bfs()
{
	q.push((xxx){1,1,0,1});
	vis[1][1]=1;
	while(!q.empty())
	{
		xxx now;
		now=q.top();
		q.pop();
		if(now.x==n&&now.y==n)
		{
			return ;
		}
		int dx[4]={0,0,1,-1};
		int dy[4]={-1,1,0,0};
		for(int i=0;i<4;i++)
		{
			int tx,ty;
			tx=now.x+dx[i];
			ty=now.y+dy[i];
			if(tx>0&&ty>0&&tx<=n&&ty<=n&&vis[tx][ty]==0)
			{
				if(g[tx][ty]==-1)
				{
					if(now.flag==1)
					{
						vis[tx][ty]=1;
						xxx sum=q.top();
						q.push((xxx){tx,ty,now.val+2,0});
					}
				}
				else
				{
					if(g[tx][ty]!=g[now.x][now.y])
					{
						vis[tx][ty]=1;
						q.push((xxx){tx,ty,now.val+1,1});
					}
					if(g[tx][ty]==g[now.x][now.y])
					{
						vis[tx][ty]=1;
						q.push((xxx){tx,ty,now.val+0,1});
					}
				}
			}
		}
	}
}
int main()
{
	memset(g,-1,sizeof(g));
	scanf("%d%d",&n,&m);
	xxx tmp;
	for(int i=1;i<=m;i++)
	{
		int tmp1;
		scanf("%d%d%d",&tmp.x,&tmp.y,&tmp1);
		g[tmp.x][tmp.y]=tmp1;
	}
	bfs();
	xxx tmp1=q.top();
	if(tmp1.x==n&&tmp1.y==n)
	{
		printf("%d",tmp1.val);
	}
	else
	{
		printf("-1");
	}
    return 0;
}

样例一输出9