#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r,step) for(int i=(l);i<(r);i+=step) 
#define per(i,l,r,step) for(int i=(r);i>(l);i-=step)

int m,t[50010],T,d;
int _time,_x,_y,x,y;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
struct meteor{
	int time,x,y;
}met[310];
bool cmp(struct meteor a,struct meteor b){
	return a.time<b.time;
}
bool mp[2][310][310];
bool valid(int X,int Y,int c){
	return X>=0&&X<=300&&Y>=0&&Y<=300&&mp[c][X][Y]==false;//标记陨石掉落&bessie行走（不走环） 
}
int main(){
	scanf("%d",&m);
	rep(i,0,m,1){
		scanf("%d%d%d",&_x,&_y,&_time);
		met[i].time=_time,met[i].x=_x,met[i].y=_y;
		mp[1][_x][_y]=true;
		rep(j,0,4,1){
			_x+=dx[j];
			_y+=dy[j];
			if(valid(_x,_y,1)) mp[1][_x][_y]=true;
			_x-=dx[j];
			_y-=dy[j];
		}
	}
	_time=-1;
	sort(met,met+m,cmp);//按时间从小到大排序 
	queue<pair<pair<int,int>,int> > q;
	q.push(make_pair(make_pair(0,0),0));
	mp[0][0][0]=true;
	while(q.size()){
		x=q.front().first.first;
		y=q.front().first.second;
		T=q.front().second;
		q.pop();
		if(mp[1][x][y]==false){//bessie runs to safe place
			_time=T;
			break;
		}
		while(T==met[d].time){//meteor fells
			rep(i,0,4,1){
				_x=met[d].x;
				_y=met[d].y;
				met[d].x+=dx[i];
				met[d].y+=dy[i];
				if(valid(met[d].x,met[d].y,0)) mp[0][met[d].x][met[d].y]=true;
				met[d].x=_x;
				met[d].y=_y;
			}
			d++;
		}
		rep(i,0,4,1){//Bessie walk
			_x=x;
			_y=y;
			x+=dx[i];
			y+=dy[i];
			if(valid(x,y,0)){
				mp[0][x][y]=true;
				q.push(make_pair(make_pair(x,y),T+1));
			}
			x=_x;
			y=_y;
		}	
	}
	printf("%d\n",_time);
}