#include<bits/stdc++.h>
#define inf 0x7fffffff
using namespace std;
int n,f[310][310];
bool mark[310][310];
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
struct data
{int x,y,t;}q[90001];
void bfs()
{
	int t=0,w=1;
	mark[0][0]=1;
	while(t<w)
	{
		int x=q[t].x,y=q[t].y,time=q[t].t;
		t++;
		for(int i=0;i<4;i++)
		{
			int x1=x+xx[i],y1=y+yy[i];
			if(mark[x1][y1]||x1<0||y1<0||time+1>=f[x1][y1])
			continue;
            if(f[x1][y1]==inf)
			{
			    cout<<time+1<<endl;;
				return;
			}
			q[w].x=x1;
			q[w].y=y1;
			q[w++].t=time+1;
			mark[x1][y1]=1;
		}
	}
	
}
int main()
{
	freopen("meteor.in","r",stdin);
    freopen("meteor.out","w",stdout);
	for(int i=0;i<=305;i++)
	for(int j=0;j<=305;j++)
	f[i][j]=inf;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x,y,t;
		cin>>x>>y>>t;
		f[x][y]=min(f[x][y],t);
		for(int j=0;j<4;j++)
		{
			int x1=x+xx[j],y1=y+yy[j];
			if(x1<0||y1<0)
			continue;
			f[x1][y1]=min(f[x1][y1],t);
		}
	}
	bfs();
	return 0; 
}