#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
const int MAX_H=300,MAX_M=300,M=50000,INF=10000;
int last=0;
int dx[5]={1,0,0,-1,0};
int dy[5]={0,-1,1,0,0};
int dp[MAX_H][MAX_M];
int a[MAX_H][MAX_M];
struct Metor
{
	int x,y,t;
};
Metor m[M];
typedef Metor P;
int bfs()
{
	memset(dp, 0, sizeof(dp));
	queue<P> que;
	P now;
	now.x=0;
	now.y=0;
	now.t=0;
	que.push(now);
	while(que.size())
	{
		P p=que.front();
		que.pop();
		for(int j=0;j<4;j++)
		{
			p.x=p.x+dx[j];
			p.y=p.y+dy[j];
			p.t++;
			if(p.x>=0 && p.y>=0 && a[p.y][p.x]>p.t && !dp[p.y][p.x])
			{
				dp[p.y][p.x]=1;
				if(a[p.y][p.x]>last)
				{
					return p.t;
				}
				que.push(p);
			}
		}
	}
	return -1;
}

int main()
{
	scanf("%d",&M);
	for(int i=0;i<M;i++)
	{
		scanf("%d%d%d",&m[i].x,&m[i].y,&m[i].t);
	}
	memset(a,INF,sizeof(a));
	for(int i=0;i<M;i++)
	{
		last=max(last,m[i].t);
		for(int j=0;j<5;j++)
		{
			int nx=m[i].x+dx[i];
			int ny=m[i].y+dy[i];
			if(nx>=0 && ny>=0 && a[ny][nx]>m[i].t)
			{
				a[ny][nx]=m[i].t;
			}
		}
	}
	if(a[0][0]==0)
	{
		printf("-1\n");
	}
	else
	{
		printf("%d\n",bfs());
	}
	return 0;
}