#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
queue <PII> q;
int map[400][400];
int safe[400][400];
int d[5]={-1,0,1,0,-1};
int dx,dy;
int bfs()
{
	q.push({0,0});
	if(!safe[0][0]) return map[0][0];
	while(!q.empty())
	{
		PII u=q.front();
		q.pop();
		for(int i=0;i<5;i++)
		{
			dx=u.x+d[i],dy=u.y+d[i+1];
			if(dx<0||dy<0) continue;
			if(map[u.x][u.y]+1<map[dx][dy])
			{
				map[dx][dy]=map[u.x][u.y]+1;
				if(!safe[dx][dy]) return map[dx][dy];
				q.push({dx,dy});
			}
		}
	}
	return -1;
}
int main()
{
	for(int i=0;i<=310;i++)
	for(int j=0;j<=310;j++) map[i][j]=100000010;
	map[0][0]=0;
	int n,x,y,t;
	cin>>n;
	while(n--)
	{
		cin>>x>>y>>t;
		map[x][y]=min(map[x][y],t);
		safe[x][y]=1;
		for(int i=0;i<5;i++)
		{
			if(x+d[i]<0||y+d[i+1]<0) continue;
			map[x+d[i]][y+d[i+1]]=min(map[x+d[i]][y+d[i+1]],t);
			safe[x+d[i]][y+d[i+1]]=1;
		}
	}
	cout<<bfs()<<endl;
}