#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
int dx[4] = {-1,1,0,0};int dy[4] = {0,0,1,-1};
int time1[300][300];bool visit[300][300];
int meteor[300][300];
struct cow1{
	int x,y;
};
queue<cow1> Q;
int main()
{
memset(meteor,-1,sizeof(meteor));
int M,time2 = 0,maxtime = -1;
cin >> M;
for(int i = 0;i < M;i++)
	{
		int tmpx,tmpy,t;
		cin >> tmpx >> tmpy >> t;
		meteor[tmpx][tmpy] = t;
		if(tmpx + 1 <= 300) 
 		meteor[tmpx + 1][tmpy] = t;
		if(tmpx - 1 >= 0)
		meteor[tmpx - 1][tmpy] = t;
		if(tmpy + 1 <= 300)
		meteor[tmpx][tmpy + 1] = t;
		if(tmpy - 1 >= 0)
		meteor[tmpx][tmpy - 1] = t;
		if(t > maxtime) maxtime = t;
	}
	//cout << maxtime << endl;
cow1 start;
start.x = 0;start.y = 0;
visit[0][0] = true;
Q.push(start);
while(!Q.empty())
{
	cow1 f = Q.front();
    Q.pop();
    if(time1[f.x][f.y] >= maxtime) break;
    for(int i = 0;i < 4; i++)
    {
    	int ux = f.x + dx[i];int uy = f.y + dy[i];
    	if(ux >= 0&&ux <= 300&&uy >= 0&&uy <= 300)
    	{
    	time1[ux][uy] = time1[f.x][f.y] + 1;
    	if(meteor[ux][uy] > time1[ux][uy]&&visit[ux][uy] == false)
    	{
    		time2 = time1[ux][uy];
    		visit[ux][uy] = true;
		    cow1 tp = {ux,uy};
		    Q.push(tp);
		}
	    }
    }
}
cout << time2 + 1;
return 0;
}