using namespace std;
int n,m,ans=1e9;
int pic[1010][1010];
int vis[1010][1010];
int fx[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
queue<pair<int ,int > > q;
int main(){
	int t;
	cin>>t;
	for(int i=0;i<=1000;i++){
		for(int j=0;j<=1000;j++){
			pic[i][j]=-1;
		}
	}
	for(int i=1;i<=t;i++){
		int x,y,tx;
		cin>>x>>y>>tx;
		pic[x][y]=tx;
		for(int i=0;i<4;i++){
			int xx=x+fx[i][0];
			int yy=y+fx[i][1];
			if(xx>=0&&yy>=0){
				if(pic[xx][yy]!=-1) pic[xx][yy]=min(pic[xx][yy],tx);
				else pic[xx][yy]=tx;
			}
		}
		n=max(x,n);
		m=max(y,m);
	}
	n++;m++;
	n++;m++;
	memset(vis,0,sizeof(vis));
	q.push(make_pair(0,0));
	while(!q.empty()){
		int x=q.front().first;
		int y=q.front().second;
		int tt=vis[x][y]+1;
		q.pop();
		for(int i=0;i<4;i++){
			int xx=x+fx[i][0];
			int yy=y+fx[i][1];
			if(!vis[xx][yy]&&(tt<pic[xx][yy]||pic[xx][yy]==-1)&&xx>=0&&yy>=0&&xx<=n&&y<=m){
				vis[xx][yy]=tt;
				q.push(make_pair(xx,yy));
			}
		}
	}
//	cout<<"\n";
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
//			cout<<setw(3)<<vis[i][j]<<" ";
			if(vis[i][j]&&pic[i][j]==-1) ans=min(ans,vis[i][j]);
		}//cout<<"\n";
	}//cout<<"\n";
/*	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			cout<<setw(3)<<pic[i][j]<<" ";
		}cout<<"\n";
	}cout<<"\n";*/
	if(ans==1e9) cout<<-1;
	else cout<<ans;
}```