#include<bits/stdc++.h>
using namespace std;
int n,x,y,t;
int ma[301][301],v[301][301],ans[301][301];
int dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};
bool flag=true;
queue<int> q[2];
int ch(int a){
	if(a==-1) return 99999;
	else return a;
}
int main(){
    cin>>n;
    for(int i=0;i<301;i++){
    	for(int j=0;j<301;j++) ma[i][j]=-1;
	}
    for(int i=1;i<=n;i++){
    	cin>>x>>y>>t;
		for(int j=0;j<=4;j++){
			if(x+dx[j]>=0&&y+dy[j]>=0&&(ma[x+dx[j]][y+dy[j]]==-1||ma[x+dx[j]][y+dy[j]]>t)) ma[x+dx[j]][y+dy[j]]=t;
		} 
	}
	v[0][0]=1;
	q[0].push(0),q[1].push(0);
	while(!q[0].empty()){
		int tx=q[0].front(),ty=q[1].front();
		q[0].pop(),q[1].pop();
		int s=ans[tx][ty]+1;
		if(ma[tx][ty]==-1){ 
			cout<<s-1;
			flag=false;
			break;
		}
		for(int i=1;i<=4;i++){
			int sx=tx+dx[i],sy=ty+dy[i];
			if(sx>=0&&sy>=0&&s<ch(ma[sx][sy])&&v[sx][sy]==0){
				q[0].push(sx),q[1].push(sy);
				v[sx][sy]=1,ans[sx][sy]=s;
			}
		}
	}
	if(flag) cout<<-1;
	return 0;
}