#include<bits/stdc++.h>
using namespace std;
int m;
int mp[305][305];
bool v[305][305]; 
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
struct node{
	int x,y,step;
};
void BFS(){
	v[0][0]=true;
	queue<node>q;
	node k;
	k.step=0;
	k.x=0;
	k.y=0;
	q.push(k);
	while(q.size()){
		node r=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int ddx=dx[i]+r.x;
			int ddy=dy[i]+r.y;
			if(ddx>=0&&ddy>=0&&ddx<=301&&ddy<=301&&(r.step+1<mp[ddx][ddy]||mp[ddx][ddy]==0)&&!v[ddx][ddy]){
				if(!mp[ddx][ddy]){
					cout<<r.step+1;
					return;
				}
				v[ddx][ddy]=true;
				k.step=r.step+1;
				k.x=ddx;
				k.y=ddy;
				q.push(k);
			}
		}
	}
	cout<<-1;
}
int main(){
	cin>>m;
	int a,b,c;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		if(mp[a][b])mp[a][b]=min(mp[a][b],c);
		else mp[a][b]=c;
		for(int j=0;j<4;j++){
			int da=a+dx[j];
			int db=b+dy[j];
			if(da>=0&&db>=0){
				if(mp[da][db])mp[da][db]=min(mp[da][db],c);
				else mp[da][db]=c;
			} 
		}
	}
	BFS();
	return 0;
}