#include<bits/stdc++.h>
#include<limits.h>
using namespace std;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int a[500][500],m,xi,yi,ti,nx,ny,nt,vis[500][500];
struct node{
	int x,y,t;
};
queue<node> q;
node tmp;
int main(){
	cin>>m;
	for(int i=0;i<=305;i++){
		for(int j=0;j<=305;j++){
			a[i][j]=10000;
		}
	}
	for(int i=1;i<=m;i++){
		cin>>xi>>yi>>ti;
		if(ti<a[xi][yi]){
			a[xi][yi]=ti;
		}
		for(int j=0;j<4;j++){
			if(ti<a[xi+dx[j]][yi+dy[j]]){
				a[xi+dx[j]][yi+dy[j]]=ti;
			}
		}
	}	
	tmp=(node){0,0,0};
	q.push(tmp);
	vis[0][0]=1;
	while(!q.empty()){
		tmp=q.front();
		q.pop();
		xi=tmp.x;
		yi=tmp.y;
		ti=tmp.t;
		if(a[xi][yi]==10000){
			break;
		}
		for(int i=0;i<4;i++){
			nx=xi+dx[i];
			ny=yi+dy[i];
			nt=ti+1;
			if(nx>=0&&ny>=0&&nt<a[nx][ny]&&vis[nx][ny]==0){
					vis[nx][ny]=1;
					q.push((node){nx,ny,nt});
			}
		}
	}
	if(a[xi][yi]==10000){
		cout<<ti;	
    }		
	else{
		cout<<-1;
	}
	return 0;
}