#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=310;
struct Node{
	int x,y,sum;
};
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int a[N][N];
queue<Node> q;
int bfs(){
	Node v;
	v.x=0; v.y=0; v.sum=0;
	q.push(v);
	while(!q.empty()){
		Node t=q.front();
		q.pop();
		int tx=t.x,ty=t.y,res=t.sum;
		if(a[tx][ty]==-1) return res;
		for(int i=0;i<4;i++){
			int nx=tx+dx[i],ny=ty+dy[i];
			if(nx>=0&&ny>=0&&(a[nx][ny]==-1||a[nx][ny]>res+1)){
				Node k;
				k.x=nx; k.y=ny; k.sum=res+1;
				q.push(k);
			}
		}
	}
	return -1;
}
int main(){
	memset(a,-1,sizeof a);
	int m;
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int x,y,t;
		scanf("%d%d%d",&x,&y,&t);
		a[x][y]=t;
		for(int j=0;j<4;j++){
			int tx=x+dx[j],ty=y+dy[j];
			if(tx>=0&&ty>=0){
				if(a[tx][ty]==-1) a[tx][ty]=t;
				else a[tx][ty]=min(a[tx][ty],t);
			}
		}
	}
	int ans=bfs();
	printf("%d",ans);
	return 0;
}