#include<bits/stdc++.h>
using namespace std;
int vist[1010][1010];
struct node{
	int x,y;
	int step;
	int t=INT_MAX;
	int lx;
}a[1010][1010],duile[1010010];
int dx[]={1,-1,0,0};
int dy[]={0,0,-1,1};
void bfs(){
	int l=1,r=0;
	vist[0][0]=1;
	duile[++r].x=0;
	duile[r].y=0;
	duile[r].step=0;
	while(l<=r){
		int nowx=duile[l].x;
		int nowy=duile[l].y;
		int nstep=duile[l].step;
		if(a[nowx][nowy].lx==0){
			cout<<nstep;
			return;
		}
		for(int i=0;i<4;i++){
			int nextx=nowx+dx[i];
			int nexty=nowy+dy[i];
			if(nextx>=0&&nexty>=0&&!vist[nextx][nexty]){
				if(a[nextx][nexty].lx==1&&a[nextx][nexty].t==nstep+1){
					l=l+0;
				}
				else{
					vist[nextx][nexty]=1;
					duile[++r].x=nextx;
					duile[r].y=nexty;
					duile[r].step=nstep+1;
				}
			}
		}
		l++;
	}
	cout<<-1;
}
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int a1,b1,c1;
		cin>>a1>>b1>>c1;
		a[a1][b1].lx=1;
		a[a1+1][b1].lx=1;
		if(a1-1>=0)
		a[a1-1][b1].lx=1;
		if(b1-1>=0)
		a[a1][b1-1].lx=1;
		a[a1][b1+1].lx=1;
		a[a1][b1].t=min(a[a1][b1].t,c1);
		a[a1+1][b1].t=min(a[a1+1][b1].t,c1);
		if(a1-1>=0)
		a[a1-1][b1].t=min(a[a1-1][b1].t,c1);
		if(b1-1>=0)
		a[a1][b1-1].t=min(a[a1][b1-1].t,c1);
		a[a1][b1+1].t=min(a[a1][b1+1].t,c1);
	}
	bfs();
}