#14WA啦,请求大佬求调

#include <bits/stdc++.h>
using namespace std;
int vis[1010][1010],m,i,j,fxx[4]= {1,-1,0,0},fxy[4]= {0,0,1,-1},ttt,last,minn=1000000;
struct kkk {
    int x1,y1,z1;
} a[500010];
struct stu {
    int xt,yt,tt;
};
bool cmp(kkk k1,kkk k2) {
    if(k1.z1<k2.z1) return 1;
    return 0;
}
void bfs() {
    stu now;
    stu next;
    now.xt=0;
    now.yt=0;
    now.tt=0;
    last=0;
    ttt=0;
    queue<stu> jl;
    jl.push(now);
    vis[0][0]=-100;
    for(ttt=1; ttt<=(a[m-1].z1); ttt++) {
        while((ttt>=a[last].z1)&&(last<m)) {
            vis[a[last].x1][a[last].y1]=-1;
            if(a[last].x1-1>=0) {
                vis[a[last].x1-1][a[last].y1]=-1;
            }
            if(a[last].x1+1<=300) {
                vis[a[last].x1+1][a[last].y1]=-1;
            }
            if(a[last].y1+1<=300) {
                vis[a[last].x1][a[last].y1+1]=-1;
            }
            if(a[last].y1-1>=0) {
                vis[a[last].x1][a[last].y1-1]=-1;
            }
            last++;
        }
        while((!jl.empty())&&((jl.front()).tt+1<=ttt)) {
            now=jl.front();
            jl.pop();
            next.tt=now.tt+1;
            for(j=0; j<4; j++) {
                next.xt=now.xt+fxx[j];
                next.yt=now.yt+fxy[j];
                if((next.xt>=0)&&(next.xt<=300)&&(next.yt>=0)&&(next.yt<=300)&&(vis[next.xt][next.yt]==0)) {
                    jl.push(next);
                    vis[next.xt][next.yt]=next.tt;
                }
            }

        }
    }
    return ;
}
int main() {
    scanf("%d",&m);
    for(i=0; i<m; i++) {
        scanf("%d%d%d",&a[i].x1,&a[i].y1,&a[i].z1);
    }
    sort(a,a+m,cmp);
    bfs();
    for(i=0; i<=300; i++) {
        for(j=0; j<=300; j++) {
            if(vis[i][j]==-100) {
                minn=0;
                printf("0");
                break;
            }
            if(vis[i][j]>0) {
                minn=min(minn,vis[i][j]);
            }
        }
    }
    if((minn!=1000000)&&(minn!=0)) printf("%d",minn);
    else if(minn==1000000) printf("-1");
    return 0;
}