#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
struct pt{
	int px,py,t;
};
queue<pt> q;
int tx[5]={0,0,-1,1};
int ty[5]={-1,1,0,0};
int map[500][500];
int vst[500][500];
int m,ans=-1;
bool flag;
void bfs(){
	while(!q.empty()){
		pt now=q.front();
		if(map[now.px][now.py]==INF){
			ans=now.t;
			break;
		}
		for(int i=0;i<4;i++){
			pt nxt;
			nxt.px=now.px+tx[i];
			nxt.py=now.py+ty[i];
			nxt.t=now.t+1;
			if(nxt.px>=0&&nxt.px<=450&&nxt.py>=0&&nxt.py<=450&&nxt.t<map[nxt.px][nxt.py]&&vst[nxt.px][nxt.py]==0){
				vst[nxt.px][nxt.py]=1;
				q.push(nxt);
				//cout<<nxt.px<<" "<<nxt.py<<endl;
			}
		}
		q.pop();
	}
}
int main(){
	memset(map,INF,sizeof(map));
	cin>>m;
	while(m--){
		int sx,sy,st;
		cin>>sx>>sy>>st;
		map[sx][sy]=st;
		for(int i=0;i<4;i++){
			if(sx+tx[i]<0||sy+ty[i]<0) continue;
			map[sx+tx[i]][sy+ty[i]]=min(st,map[sx+tx[i]][sy+ty[i]]);
		}
	}
	pt start{0,0,0};
	q.push(start);
	vst[0][0]=1;
	bfs();
	cout<<ans;
	return 0;	
}