#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXM=50010,MAXX=310;
struct Star
{
    int X,Y,T;
}stars[MAXM];
int M,ans=-1,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
queue<int> x,y,t;
bool map[MAXX][MAXX],mapf[MAXX][MAXX],vis[MAXX][MAXX];
bool cmp(Star a,Star b);
void bfs();
int main()
{
    scanf("%d",&M);
    for(int i=1;i<=M;i++)
    {
        scanf("%d%d%d",&stars[i].X,&stars[i].Y,&stars[i].T);//输入部分
    }
    sort(stars+1,stars+M+1,cmp);//输入完进行排序方便模拟
    // for(int i=1;i<=M;i++)
    // {
    //     printf("Stars:X=%d Y=%d T=%d\n",stars[i].X,stars[i].Y,stars[i].T);
    // }
    for(int i0=1;i0<=M;i0++)
    {
        int sdx=stars[i0].X,sdy=stars[i0].Y,nx,ny;
        mapf[sdx][sdy]=true;
        for(int i=0;i<4;i++)
        {
            nx=sdx+dx[i];
            ny=sdy+dy[i];
            mapf[nx][ny]=true;
        }
    }
    bfs();//开始搜索
    printf("%d",ans);//输出
    return 0;
}
void bfs()
{
    int nowx,nowy,nowt,nowstar=1,nxtx,nxty,nxtt,nxtstar;
    x.push(0);//初始状态放入队列
    y.push(0);
    t.push(0);
    while(!x.empty())
    {
        nowx=x.front();//取出
        nowy=y.front();
        nowt=t.front();
        x.pop();//删除
        y.pop();
        t.pop();
        if(vis[nowx][nowy]==true)
            continue;//跳过重复搜索
        vis[nowx][nowy]=true;
        // printf("x=%d y=%d t=%d\n",nowx,nowy,nowt);
        if(!(nowx==0&&nowy==0)&&mapf[nowx][nowy]==false/*无流星的区域*/||(nowstar>M&&nowt!=stars[nowstar-1].T/*最后一个流星标完还要继续搜*/)/*流星落完了*/)
        {
            ans=nowt;
            return;
        }
        while(nowt==stars[nowstar].T)//先标记流星
        {
            int sdx=stars[nowstar].X,sdy=stars[nowstar].Y,nx,ny;
            map[sdx][sdy]=true;
            for(int i=0;i<4;i++)
            {
                nx=sdx+dx[i];
                ny=sdy+dy[i];
                map[nx][ny]=true;
            }
            nowstar++;//下一个
            //不设循环可能漏
        }
        //有被流星突然炸死的可能
        if(map[nowx][nowy]==true)//被炸死直接重开吧
            continue;
        nxtt=nowt+1;
        for(int i=0;i<4;i++)
        {
            nxtx=nowx+dx[i];
            nxty=nowy+dy[i];
            if(nxtx>=0&&nxty>=0&&map[nxtx][nxty]==false)//可以经过
            {
                x.push(nxtx);
                y.push(nxty);
                t.push(nxtt);
            }
        }
    }
}
bool cmp(Star a,Star b)
{
    if(a.T<b.T)
        return true;
    else
        return false;
}