#include <bits/stdc++.h>
using namespace std;
int ti[400][400];
int ans[400][400];

int Ans=9999999;
int walk[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
struct coord{
    int x,y;
};
int main()
{
    memset(ans,-1,sizeof (ans));
    memset(ti,999999,sizeof (ti));
    ans[0][0]=0;

    int M;
    cin >> M;

    while (M--)
    {
        int x,y,t;
        cin >>x >> y >> t;
        printf("ok");
        ti[x][y]=min(t,ti[x][y]);
        for(int j=0;j<4;j++)
        {
            ti[x+walk[j][0]][y+walk[j][1]]=min(t,ti[x+walk[j][0]][y+walk[j][1]]);
        }
    }
    printf("ok\n");
    queue<coord>Q;

    Q.push((coord){0,0});

    while (!Q.empty())
    {
        int ux=Q.front().x;
        int uy=Q.front().y;

        int t=ans[ux][uy];

        Q.pop();

        for(int j=0;j<4;j++)
        {
            int x=ux+walk[j][0];
            int y=uy+walk[j][1];
            if (x < 0 ||x>300|| y < 0 ||y>300|| ans[x][y] != -1 || t +1>= ti[x][y])
                continue;
            ans[x][y]=t+1;
            Q.push((coord){x,y});
        }
    }
    for(int i=0;i<=305;i++)
    {
        for(int j=0;j<=305;j++)
        {
            if(ti[i][j]>5000&&ans[i][j]!=-1)
                Ans=min(Ans,ans[i][j]);
        }
    }
    if(Ans==999999)
        puts("-1");
    else
        printf("%d",Ans);
    return 0;
}