#include<bits/stdc++.h>
using namespace std;
const int N=50010,M=310;
int n,x[N],y[N],t[N],ans=1e9,mp[M][M];
bool vis[M][M];
struct node{int x,y,t;}a[N];
queue<node>q;
bool cmp(node a,node b){return a.t<b.t;}
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
bool check(int x,int y){
	if(x<1||x>M+1||y<1||y>M+1||vis[x][y]||mp[x][y]==1)return 0;
	else return 1;
}
int bfs(int nx,int ny){
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=M+1;++i){
		for(int j=1;j<=M+1;++j){
			if(mp[i][j]==1)mp[i][j]=0;
		}
	}
	while(q.size())q.pop();
	q.push({0,0,0});
	while(q.size()){
		node now=q.front();
		q.pop();
		for(int i=0;i<4;++i){
			int xx=dx[i]+now.x;
			int yy=dy[i]+now.y;
			int l=0,r=n,mid;
			while(l<=r){
				mid=l+r>>1;
				if(a[mid].t<now.t+1)l=mid+1;
				else r=mid-1;
			}
			if(a[r].t==now.t+1){
				mp[a[r].x][a[r].y]=1;
				mp[a[r].x+1][a[r].y]=1;
				mp[a[r].x-1][a[r].y]=1;
				mp[a[r].x][a[r].y+1]=1;
				mp[a[r].x][a[r].y-1]=1;
			}
			if(!check(xx,yy))continue;
			q.push({xx,yy,now.t+1});
			vis[xx][yy]=1;
			if(xx==nx&&yy==ny)return now.t+1;
		}
	}
	return 1e9;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
		mp[a[i].x][a[i].y]=2;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=M+1;++i){
		for(int j=1;j<=M+1;++j){
			if(mp[i][j]!=2)ans=min(ans,bfs(i,j));
		}
	}
	if(ans==1e9)cout<<-1;
	cout<<ans;
	return 0;
}