#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define ks(x,y) x=max(x,y);
using namespace std;
int m[512][512];
int go[512][512];
int n,maxt,maxx,maxy;
int fns[2][4]={{1,-1,0,0},{0,0,1,-1}};//方向 
int times,maxans=131072;
void bfs(int x,int y)
{
	if(x<=-1||y<=-1||times>=maxans||((times)>=m[x][y]&&m[x][y]!=-1)||go[x][y]==1)	return;
	go[x][y]=1;
	if(m[x][y]==-1)	{maxans=min(maxans,times);return;}//存储最短时间 
	for(int i=0;i<4;i++)
	{
		times++;
		bfs(x+fns[0][i],y+fns[1][i]);
		go[x+fns[0][i]][y+fns[1][i]]=0;
		times--;
	}
}
int main()
{
	cin>>n;
	memset(m,-1,sizeof(m));
	for(int i=1;i<=n;i++)
	{
		int X,Y,T;
		scanf("%d%d%d",&X,&Y,&T);
		m[X][Y]=m[X][Y]==-1?T:min(m[X][Y],T);
		if(X!=0)	m[X-1][Y]=m[X-1][Y]==-1?T:min(m[X-1][Y],T);
		m[X+1][Y]=m[X+1][Y]==-1?T:min(m[X+1][Y],T);
		m[X][Y+1]=m[X][Y+1]==-1?T:min(m[X][Y+1],T);
		if(Y!=0)	m[X][Y-1]=m[X][Y-1]==-1?T:min(m[X][Y-1],T);//最短到达的时间 
		ks(maxx,X);ks(maxy,Y);ks(maxt,T);
	}
	bfs(0,0);
	printf("%d",maxans==131072?-1:maxans);
	return 0;
}

rt，T了5个点