#include <bits/stdc++.h>
using namespace std;
int vis[1010][1010],m,i,j,fxx[4]= {1,-1,0,0},fxy[4]= {0,0,1,-1},ttt,last,minn=1000000;
struct kkk {
	int x1,y1,z1;
} a[500010];
struct stu {
	int xt,yt,tt;
};
bool cmp(kkk k1,kkk k2) {
	if(k1.z1<k2.z1) return 1;
	return 0;
}
void bfs() {
	stu now;
	stu next;
	now.xt=0;
	now.yt=0;
	now.tt=0;
	last=0;
	ttt=0;
	queue<stu> jl;
	jl.push(now);
	vis[0][0]=-100;
	for(ttt=1; ttt<=(a[m-1].z1); ttt++) {
		while((ttt>=a[last].z1)&&(last<m)) {
			vis[a[last].x1][a[last].y1]=-1;
			if(a[last].x1-1>=0) {
				vis[a[last].x1-1][a[last].y1]=-1;
			}
			if(a[last].x1+1<=300) {
				vis[a[last].x1+1][a[last].y1]=-1;
			}
			if(a[last].y1+1<=300) {
				vis[a[last].x1][a[last].y1+1]=-1;
			}
			if(a[last].y1-1>=0) {
				vis[a[last].x1][a[last].y1-1]=-1;
			}
			last++;
		}
		while((!jl.empty())&&((jl.front()).tt+1<=ttt)) {
			now=jl.front();
			jl.pop();
			next.tt=now.tt+1;
			for(j=0; j<4; j++) {
				next.xt=now.xt+fxx[j];
				next.yt=now.yt+fxy[j];
				if((next.xt>=0)&&(next.xt<=300)&&(next.yt>=0)&&(next.yt<=300)&&(vis[next.xt][next.yt]==0)) {
					jl.push(next);
					vis[next.xt][next.yt]=next.tt;
				}
			}

		}
	}
	return ;
}
int main() {
	scanf("%d",&m);
	for(i=0; i<m; i++) {
		scanf("%d%d%d",&a[i].x1,&a[i].y1,&a[i].z1);
	}
	sort(a,a+m,cmp);
	bfs();
	for(i=0; i<=300; i++) {
		for(j=0; j<=300; j++) {
			if(vis[i][j]==-100) {
				minn=0;
				printf("0");
				break;
			}
			if(vis[i][j]>0) {
				minn=min(minn,vis[i][j]);
			}
		}
	}
	if((minn!=1000000)&&(minn!=0)) printf("%d",minn);
	else if(minn==1000000) printf("-1");
	return 0;
}