#include <bits/stdc++.h>
using namespace std;
int f[1005][1005], c[1005][1005], m, n;
int dy[4]={1,0,1,0}, dx[4]={0,-1,0,1};
void DFS(int x,int y,bool ma)
{
	for(int i=1;i<4;i++)
	{
		const int tx=dx[i]+x;
		const int ty=dy[i]+y;
		if(tx>=1&&tx<=m&&ty>=1&&ty<=m)
		{
			if(f[tx][ty]==0)
				if(c[x][y]+2<c[tx][ty]&&!ma)
				{
					f[tx][ty]=f[x][y];
					c[tx][ty]=c[x][y]+2;
					DFS(tx,ty,true);
					f[tx][ty]=0;
				}
			else if(f[tx][ty]!=f[x][y])
			{
				if(c[tx][ty]>c[x][y]+1)
				{
					c[tx][ty]=c[x][y]+1;
					DFS(tx,ty,false);
				}			
			}
			else
			{
				if(f[x][y]<f[tx][ty])
				{
					f[tx][ty]=f[x][y];
					DFS(tx,ty,false);
				}
			}
		}
	}
}
int main()
{	
	memset(c,0x3f,sizeof(c)); 
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{	
		int x, y, z;
		cin>>x>>y>>z;
		f[x][y]=z+1;
	}
	DFS(1,1,0);
    c[1][1]=0;
	if(c[m][n]==0x3f3f3f3f)out<<-1;
	else cout<<f[m][m];
	return 0;
}

求帮忙