#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f; 
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int m;
int a[510][510];
bool vis[510][510];//bfs的特性，同一时间走到一个点没必要重复拓展。 
int dd[510][510];//标记这个格子什么时候会被炸毁
struct node{
	int x,y,day;
};
void bfs()
{
	queue<node> q;
	q.push((node){0,0,0});
	while(q.size())
	{
		node u=q.front();
		q.pop();
		int x=u.x;
		int y=u.y;
		int day=u.day;
		if(dd[x][y]==INF)
		{
			cout<<day;
			exit(0);
		}
		for(int i=0;i<4;i++)
		{
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(xx<0||yy<0||xx>300||yy>300)
			continue;
			if((day<dd[xx][yy]-1)&&(!vis[xx][yy]))//走到那里的时候不会被砸死
			{
				vis[xx][yy]=1;
				q.push((node){xx,yy,day+1});
			} 
		}
	}
} 
int main()
{
	cin>>m;
	memset(dd,INF,sizeof(dd));//初始全都不会炸毁 
	for(int i=1;i<=m;i++)
	{
		int x,y,t;
		scanf("%d%d%d",&x,&y,&t);
		dd[x][y]=min(dd[x][y],t);
		dd[x+1][y]=min(dd[x+1][y],t);
		dd[x-1][y]=min(dd[x-1][y],t);;
		dd[x][y+1]=min(dd[x][y+1],t);
		dd[x][y-1]=min(dd[x][y-1],t);
	}
	bfs();
	cout<<"-1";
	return 0;
}