#include <bits/stdc++.h>
using namespace std;
int n,a,b;
int m;//流星数目
int ma[500][500];//表示当前位置灰烬时间
int px[5]={0,-1,0,1,0};
int py[5]={0,0,1,0,-1};
int up=0;
int down=1;
int wx[100004];//某次序x位置
int wy[100004];//某次序y位置
int shi[100004];//某次序时间
int s=0;
int main()
{
    cin>>m;
    for(int i=0;i<=305;i++)
    {
        for(int k=0;k<=305;k++)
        {
            ma[i][k]=-1;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        int t;
        cin>>t;
        if(x>=0&&y>=0&&(ma[x][y]==-1||ma[x][y]>t))
        {
            ma[x][y]=t;
        }
        for(int z=1;z<=4;z++)
        {
            int ux=x+px[z];
            int uy=y+py[z];
            if(ux>=0&&uy>=0&&(ma[ux][uy]==-1||ma[ux][uy]>t))
            {
                ma[ux][uy]=t;
            }
        }
    }
    wx[1]=0;
    wy[1]=0;
    shi[1]=0;
    while(up<down)
    {
        up++;
        s = shi[up]+1;
        if(s>10086)
        {
            cout<<-1;
            return 0;
        }
        for(int i=1;i<=4;i++)
        {
            int x=wx[up]+px[i];
            int y=wy[up]+py[i];
            if(x>=0&&y>=0)
            {
                if(ma[x][y]==-1)
                {
                    cout<<s;
                    return 0;
                }
                else
                {
                    if(ma[x][y]>s)
                    {
                        down++;
                        wx[down]=x;
                        wy[down]=y;
                        shi[down]=s;
                    }
                }
            }
        }
    }
    cout<<-1;
    return 0;
}