#include<bits/stdc++.h>
using namespace std;
int M;
typedef struct star{//存放流星的坐标和时间 
	int x;
	int y;
	int t;
}star;
typedef struct loc{//记录当前人到达的位置 
	int x;
	int y;
}loc;
star S[50005]; 
int mp[305][305];//记录到达某个位置需要走几步，也就是需要的时间 
int vis[305][305];//是否被访问过，或被流星砸到过 
int ans; 
int move[5][5]={{-1,0},{0,1},{1,0},{0,-1},{0,0}};//移动数组 
queue<loc> q;//建立位置队列 
bool check(int X,int Y){//check函数用于检查是否永远安全，若永远安全则结束搜索，输出答案 
	for(int i=0;i<M;i++){//m个流星遍历 
		for(int j=0;j<5;j++){//流星可以砸到5个方块 
			if(X==S[i].x+move[i][0]&&Y==S[i].y+move[j][1]){
				return false;
			}
		}
	}
	//若不会被砸到说明永远安全就记录答案 
	return true;
}
void bfs(int x,int y){
	vis[x][y]=1;
	loc k,a,b;
	k.x=x;
	k.y=y;
	q.push(k);
	while(!q.empty()){ 
		a=q.front();
		q.pop();
		for(int i=0;i<M;i++){
			if(mp[a.x][a.y]==S[i].t){//到达所需的行动次数与时间相等，所以查找当前时间有无流星坠落并改变地形 
				int m,n;
				m=S[i].x+move[i][0];
				n=S[i].y+move[i][1]; 
				for(int j=0;j<5;j++){
					if(m>=0&&n>=0)
						vis[m][n]=1;//改变地形，被砸到的地方不能被访问 
				}
			}
		}
		for(int i=0;i<4;i++){
			b.x=a.x+move[i][0];
			b.y=a.y+move[i][1];
			if(check(b.x,b.y)){//若是安全的，结束循环，输出答案 
				ans=mp[a.x][a.y]+1;
				break;
			} 
			if(vis[b.x][b.y]==0&&b.x>=0&&b.y>=0){//如果没有被访问并且在范围内，则计入队列 
				mp[b.x][b.y]=mp[a.x][a.y]+1;
				q.push(b);
				vis[b.x][b.y]=1;
			}
		}
		if(check(b.x,b.y)) break;//结束while的循环 
	} 
}
int main(){
	cin>>M;
	memset(mp,-1,sizeof(mp));//初始化为-1，若不能到达则输出-1 
	memset(vis,0,sizeof(vis));//未访问则为0，访问后为1 
	for(int i=0;i<M;i++){
		cin>>S[i].x>>S[i].y>>S[i].t;
	}
	mp[0][0]=0;//起点的初始化 
	vis[0][0]=1;
	bfs(0,0);
	cout<<ans;
}