#include<bits/stdc++.h>
using namespace std;
long long int m,vis[1010][1010],dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},a[1010][1010];
struct N{
	int cnt;
	int x;
	int y;
};
int bfs(int x,int y){
	queue<N> q;
	q.push((N){0,x,y});
	vis[x][y]=1;
	while(!q.empty()){
		int u=q.front().x,v=q.front().y,dc=q.front().cnt;
		q.pop();
		for(int i=0;i<4;i++){
			int nx=u+dx[i],ny=v+dy[i];
			if(nx>=0&&ny>=0&&vis[nx][ny]==0&&(a[nx][ny]>dc+1||a[nx][ny]==-1)){
				if(a[nx][ny]==-1){
					return dc+1;
				}
				q.push((N){dc+1,nx,ny});
				vis[nx][ny]=1;
			}
		}
	}
	return -1;
}
int main(){
	cin>>m;
	memset(a,-1,sizeof(a));
	for(int i=1;i<=m;i++){
		long long int d,c,yq;
		cin>>d>>c;
		cin>>yq;
		if(a[d][c]==-1){
			a[d][c]=yq;
		}
		else{
			a[d][c]=min(a[d][c],yq);
		}
		if(a[d+1][c]==-1){
			a[d+1][c]=a[d][c];
		}
		else{
			a[d+1][c]=min(a[d+1][c],a[d][c]);	
		}
		if(a[d][c+1]==-1){
			a[d][c+1]=a[d][c];
		}
		else{
			a[d][c+1]=min(a[d][c+1],a[d][c]);	
		}
		if(d>=1){
			if(a[d-1][c]==-1){
				a[d-1][c]=a[d][c];
			}
			else{
				a[d-1][c]=min(a[d-1][c],a[d][c]);
			}
		}
		if(c>=1){
			if(a[d][c-1]==-1){
				a[d][c-1]=a[d][c];
			}
			else{
				a[d][c-1]=min(a[d][c-1],a[d][c]);
			}
		}
	}
	cout<<bfs(0,0);
	return 0;
}