#include <cstdio>

 #include <cstring>

 #include <queue>

 #include <algorithm>

 using namespace std;

 const int INF=;

 const int MAX_N=;//流星雨落在（300，300）以内，所以最近的安全点一定在（302,302）以内

 int m;

 int G[MAX_N+][MAX_N+];

 int dx[]={,,,-},dy[]={,-,,};

 int vis[MAX_N+][MAX_N+];

 struct Node

 {

     int x,y,time;

     Node(){}

     Node(int xx,int yy,int t):x(xx),y(yy),time(t){}

 };

 int inside(int x,int y)

 {

     if(x<||y<||MAX_N<x||MAX_N<y) return ;

     else return ;

 }

 int bfs()

 {

     memset(vis,,sizeof(vis));

     if(G[][]==INF) return ;

     if(G[][]==) return -;//当G[0][0]==1时，不代表没希望逃走。。。

     //因为G数组经过预处理了，把每颗流星雨的影响都表达为每个点的*时间

     queue<Node> que;

     que.push(Node(,,));

     vis[][]=;

     while(!que.empty())

     {

         Node cur=que.front();

         que.pop();

         if(G[cur.x][cur.y]==INF) return cur.time;

         for(int i=;i<;i++)

         {

             int nx=cur.x+dx[i];

             int ny=cur.y+dy[i];

             if(!inside(nx,ny)) continue;

             if(vis[nx][ny]) continue;

             if(G[nx][ny]<=cur.time+) continue;

             que.push(Node(nx,ny,cur.time+));

             vis[nx][ny]=;

         }

     }

     return -;

 }

 int main()

 {

     freopen("3669.txt","r",stdin);

     scanf("%d",&m);

     for(int i=;i<=MAX_N;i++)

         for(int j=;j<=MAX_N;j++)

             G[i][j]=INF;

     for(int i=;i<m;i++)

     {

         int x,y,t;

         scanf("%d%d%d",&x,&y,&t);

         G[x][y]=min(t,G[x][y]);

         for(int i=;i<;i++)

         {//把G数组预处理为每个点的最早*时间

             int nx=x+dx[i];

             int ny=y+dy[i];

             if(!inside(nx,ny)) continue;

             G[nx][ny]=min(t,G[nx][ny]);

         }

     }

     printf("%d\n",bfs());

     return ;

 }