#include<iostream>
#include<queue>
using namespace std;
const int N=410;
int m;
struct pos{
	int x,y,t;
};
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
bool vis[N][N][1010];
bool fall[N][N][1010];
bool unsafe[N][N];
queue<pos> q;
int main()
{
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,t;
		scanf("%d%d%d",&x,&y,&t);
		fall[x][y][t]=1;
		unsafe[x][y]=1;
		for(int i=0;i<4;i++)
		{
			int tx=x+dx[i],ty=y+dy[i];
			if(tx>=0&&ty>=0)
			{
				fall[tx][ty][t]=1;
				unsafe[tx][ty]=1;
			}
		}
	}
	if(fall[0][0][1])
	{
		puts("-1");
		return 0;
	}
	q.push({0,0,0});
	vis[0][0][0]=true;
//	vis[0][0][1]=true;
	while(!q.empty())
	{
		pos tmp=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			pos tp={tmp.x+dx[i],tmp.y+dy[i],tmp.t+1};
			if(tp.x>=0&&tp.y>=0)
				if(!fall[tp.x][tp.y][tp.t])
					if(!vis[tp.x][tp.y][tp.t])
					{
						vis[tp.x][tp.y][tp.t]=true;
						if(!unsafe[tp.x][tp.y])
						{
							printf("%d\n",tp.t);
							return 0;
						}
						
						q.push(tp);
					}
		}
	}
	puts("-1");
	return 0;
}