#include <cstdio>
#define Hello input();
#define World printf("%d",solve())
void input();
int solve();
int main()
{
	Hello World;
	return 0;
}
int n,t[50005],x[50005],y[50005];
int timeQ[3600000],xQ[3600000],yQ[3600000],head,tail=1;
bool book[605][605];
int d[2][4]={{0,0,-1,1},{-1,1,0,0}};
void input()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d%d%d",&x[i],&y[i],&t[i]);
}
bool check(int xx,int yy,int time)
{
	bool map[605][605]={};
	for(int i=0;i<n;i++)
		if(t[i]<=time)
		{
			map[x[i]][y[i]]=1;
			map[x[i]+1][y[i]]=1;
			map[x[i]-1][y[i]]=1;
			map[x[i]][y[i]+1]=1;
			map[x[i]][y[i]-1]=1;
		}
	return !map[xx][yy];
}
int solve()
{
	while(head<tail)
	{
		for(int i=0;i<4;i++)
		{
			int nx=xQ[head]+d[0][i],ny=yQ[head]+d[1][i];
			if(nx>=0 && nx<600 && ny>=0 && ny<600 && !book[nx][ny] && check(nx,ny,timeQ[head]+1))
			{
				if(check(nx,ny,1002))
					return timeQ[head]+1;
				xQ[tail]=nx;
				yQ[tail]=ny;
				timeQ[tail]=timeQ[head]+1;
				book[nx][ny]=1;
				tail++;
			}
		}
		head++;
	}
	return -1;
}