#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int mp[510][510];
bool vis[510][510];
int n,m;
struct point {
	int x,y,step;
};
int dx[4]={0,0,-1,1},dy[4]= {-1,1,0,0};
queue<point> q;
int bfs(point a) {
	q.push(a);
	vis[a.x][a.y]=1;
	while(!q.empty()) {
		point b=q.front();
		q.pop();
		for(int j=0; j<4; ++j) {
			point c;
			c.x=b.x+dx[j],c.y=b.y+dy[j],c.step=b.step+1;
			if(c.x==0||c.y==0) continue;
			if(c.x>n||c.y>n) continue;
			if(c.x==n&&c.y==n)
				return c.step;
			if(c.step<mp[c.x][c.y]&&!vis[c.x][c.y]) {
				q.push(c);
				vis[c.x][c.y]=1;
			}
		}
	}
	return -1;
}
int main() {
//	freopen("meteor.in","r",stdin);
//    freopen("meteor.out","w",stdout);
	cin>>n>>m;
	memset(mp,0x3f,sizeof(mp));
	for(int i=1,x,y,t;i<=m;i++) {
		cin>>x>>y>>t;
		mp[x][y]=min(mp[x][y],t);
		for(int j=0;j<4;j++){
			if(x+dx[j]==0||y+dy[j]==0) continue;
			if(x+dx[j]>n||y+dy[j]>n) continue;
			mp[x+dx[j]][y+dy[j]]=min(mp[x+dx[j]][y+dy[j]],t);
		}
	}
	cout<<bfs({1,1,0});
	//	fclose(stdin);
//	fclose(stdout);
	return 0;
}