#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x,y,step;
	node(int xx,int yy,int tep)
	{
		x=xx;
		y=yy;
		step=tep;
	}
};
int dx[10]={0,1,0,-1},dy[10]={1,0,-1,0},v[305][305],m,vis[305][305],ans=0x7fffffff;
queue<node> q;
inline void bfs()
{
	while(!q.empty())q.pop();
	q.push(node(0,0,0));
	vis[0][0]=1;
	while(!q.empty())
	{
		node now=q.front();
		q.pop();
		int x=now.x,y=now.y;
		if(!v[x][y])
		{
			ans=min(ans,now.step);
		}
		for(int i=0;i<4;i++)
		{
			int tx=x+dx[i],ty=y+dy[i];
			if(tx<0||ty<0||tx>=300||ty>=300)continue;
			if(vis[tx][ty]||v[tx][ty]<=now.step)continue;
			vis[tx][ty]=1;
			q.push(node(tx,ty,now.step+1));
		}
	}
}
int main()
{
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int u,V,w;
		cin>>u>>V>>w;
		v[u][V]=w;
		if(u-1>=0)
		if(!v[u-1][V])
		v[u-1][V]=w;
		else v[u-1][V]=min(v[u-1][V],w);
		v[u+1][V]=w;
		if(V-1>=0)
		if(!v[u][V-1])
		v[u][V-1]=w;
		else
		v[u][V-1]=min(v[u][V-1],w);
		if(!v[u][V+1])
		v[u][V+1]=w;
		else
		v[u][V+1]=min(v[u][V+1],w);
	}
	bfs();
	cout<<ans<<"\n";
}