#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int a[501][501],d[900001][3],ld=1,lt=1,f1,f2,f3,n,k=0;
bool bk[501][501],bkw[501][501];
void hhh(int x,int y,int z){
	if(x<0||y<0)return;
	bkw[x][y]=1;
	if(a[x][y]==0)a[x][y]=z;
	if(a[x][y]>z)a[x][y]=z;
    return;
}
void hs(int x,int y,int t){
    if(x<0||y<0)return;
	if(bk[x][y]==1||(t>=a[x][y]&&bkw[x][y]!=0))return;
	ld+=1;d[ld][0]=x;d[ld][1]=y;d[ld][2]=t;bk[x][y]=1;
	if(a[x][y]==0){
		k=1;
		cout<<d[ld][2];
	}
	return;
}
int main(){
	freopen("meteor.in","r",stdin); 
	freopen("meteor.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
	    cin>>f1>>f2>>f3;
		hhh(f1,f2,f3);
		hhh(f1+1,f2,f3);
		hhh(f1,f2+1,f3);
		hhh(f1-1,f2,f3);
		hhh(f1,f2-1,f3);
	}
	if(a[0][0]==0){cout<<"0";return 0;}
	while(lt<=ld){
	    hs(d[lt][0]+1,d[lt][1],d[lt][2]+1);if(k==1)return 0;
	    hs(d[lt][0]-1,d[lt][1],d[lt][2]+1);if(k==1)return 0;
	    hs(d[lt][0],d[lt][1]+1,d[lt][2]+1);if(k==1)return 0;
	    hs(d[lt][0],d[lt][1]-1,d[lt][2]+1);if(k==1)return 0;	
		lt+=1;
	}
	cout<<"-1";
	return 0;
}