#include<bits/stdc++.h>
using namespace std;
int m,x,y,t,a[305][305],b[305][305];
bool vis[305][305];
queue<int> qx,qy,qt;
int fx[4]={1,0,-1,0},fy[4]={0,1,0,-1};
void bfs(){
	while(!qx.empty()){
		int ox=qx.front();
		int oy=qy.front();
		int ot=qt.front();
		qx.pop();
		qy.pop();
		qt.pop();
		for(int i=0;i<4;i++){
			int nx=ox+fx[i];
			int ny=oy+fy[i];
			int nt=ot+1;
			if(b[nx][ny]!=-1&&nt>=b[nx][ny]) continue;
			if(nx>=0&&ny>=0&&!vis[nx][ny]){
				qx.push(nx);
				qy.push(ny);
				qt.push(nt);
				vis[nx][ny]=1;
				if(b[nx][ny]==-1){
					printf("%d",nt);
					exit(0);
				}
			}
		}
	}
	printf("-1\n");
}
int main(){
	cin>>m;
	memset(b,-1,sizeof(b));
	while(m--){
		cin>>x>>y>>t;
		if(b[x][y]!=-1&&t>b[x][y]) continue;
		b[x][y]=t;
		for(int i=0;i<4;i++){
			int nx=x+fx[i];
			int ny=y+fy[i];
			if(nx>=0&&ny>=0&&b[nx][ny]==-1||b[nx][ny]>t) b[nx][ny]=t;
		}
	}
	qx.push(0);
	qy.push(0);
	qt.push(0);
	vis[0][0]=1;
	if(b[0][0]==-1){
		printf("0");
		return 0;
	}
	bfs();
	return 0;
}