#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<map>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define mem(x,a) memset(x,a,sizeof(x))
#define sq(x) ((x)*(x))
const double pi=cos(-1.0);
using namespace std;

class T
{
	public:
		int x,y,t;
}a[50010];

int v[310][310];

int dir[5][2]={1,0,0,1,-1,0,0,-1,0,0};

bool u[310][310];

queue<T>Q;

bool ok(int x,int y)
{
	if(x>=0 && y>=0 && !u[x][y]) return 1;
	return 0;
}

void init()
{
	int n,i,j,tx,ty;
	
	mem(v,0);
	mem(u,0);
	
	scanf("%d",&n);
	
	for(i=0;i<n;i++)
	{
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);
	}
	
	for(i=0;i<n;i++)
		for(j=0;j<5;j++)
		{
			tx=a[i].x+dir[j][0];
			ty=a[i].y+dir[j][1];
			if(!ok(tx,ty)) continue;
			if(v[tx][ty]>a[i].t || v[tx][ty]==0) v[tx][ty]=a[i].t;	
		}	
}	

void solve()
{
	T st,cur,nt;
	
	st.x=st.y=st.t=0;
	
	u[0][0]=1;
	
	Q.push(st);
	
	if(v[0][0]==0){printf("-1\n");return;}
	
	while(!Q.empty())	
	{
		cur=Q.front();
		Q.pop();
		for(int i=0;i<4;i++)
		{
			nt.x=cur.x+dir[i][0];
			nt.y=cur.y+dir[i][1];
			nt.t=cur.t+1;
			if(ok(nt.x,nt.y))
			{
				u[nt.x][nt.y]=1;
				
				if(v[nt.x][nt.y]==0)
				{
					printf("%d\n",nt.t);
					return;
				}
				
				if(nt.t<v[nt.x][nt.y])
				{
					Q.push(nt);
				}
			}
		}
	}
	printf("-1\n");
}

int main()
{
	init();
	solve();
	system("pause");
	return 0;
}