#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
const int dx[5]={0,1,0,-1,0},dy[5]={1,0,-1,0,0};
struct ST{
	int x,y,t,pos;
	bool flag;
}map[1005][1005];
int n,x,y,t,tx,ty;
queue<ST> q;
int main(){
	cin>>n;
	for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
              map[i][j].x=i;
              map[i][j].y=j;
              map[i][j].flag=0;
              map[i][j].pos=0;
              map[i][j].t=-123456789;
        }
    }
	for(int i=1;i<=n;i++){
		cin>>x>>y>>t;
		for(int j=0;j<5;j++){
			tx=x+dx[j];
			ty=y+dy[j];
			if(tx>=0&&ty>=0){
				if(map[tx][ty].t==-123456789){
					map[tx][ty].t=t;
				}
				else{
					map[tx][ty].t=min(map[tx][ty].t,t);
				}
			}
		}
	}
	map[0][0].flag=1;
	q.push(map[0][0]);
	while(!q.empty()){
	    ST pos=q.front();
	    q.pop();
	    if(map[pos.x][pos.y].pos>=map[pos.x][pos.y].t){
	    	continue;
		}
		for(int i=0;i<5;i++){
			tx=pos.x+dx[i];
		    ty=pos.y+dy[i];
			if(tx<0||ty<0||map[tx][ty].flag) continue;
		    if(map[tx][ty].t==-12346789){
		    	cout<<map[tx][ty].pos;
		    	return 0;
			}
			map[tx][ty].flag=1;
			map[tx][ty].pos=pos.pos+1;
			q.push(map[tx][ty]);
		}
	}
}