#include<bits/stdc++.h>
using namespace std;

bool vis[305][305]; 

int m;
int fuzhu[305][305]={0};
typedef struct sss{
    int x,y,t;
}sss;
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
sss star[50005];
typedef struct ren{
    int rx,ry;
}ren;//贝茜 
ren b;
bool compare(sss s1,sss s2){
    return s1.t<s2.t;
}
void bfs(int sx, int sy, int tt) {
    queue<ren> q;
    
    q.push({sx, sy});
    vis[sx][sy] = true; // 初始位置已访问
    int step = 1;

    while (!q.empty()) {
        int size = q.size(); // 当前层的节点数量
        
        // 更新星星爆炸影响的区域
        while (step <= m && star[step].t == tt) {
           
			for (int k = 0; k < 4; ++k) {
                int nx = star[step].x + d[k][0];
                int ny = star[step].y + d[k][1];
                if (nx >= 0 && nx <= 300 && ny >= 0 && ny <= 300) {
                    vis[nx][ny]=true;
                }
            }
             vis[star[step].x][star[step].y]=true;
			// 爆炸点本身也是危险的
            
            step++;
        }
        for (int i = 0; i < size; ++i) { // 遍历当前层的所有节点
            ren c = q.front(); q.pop();
            
            // 如果当前位置是安全的，输出答案并返回
            if (fuzhu[c.rx][c.ry] == 0) {
                cout << tt << endl;
                return;
            }

            // 尝试四个方向移动
            for (int j = 0; j < 4; ++j) {
                int dx = c.rx + d[j][0];
                int dy = c.ry + d[j][1];
                if (dx >= 0 && dx <= 300 && dy >= 0 && dy <= 300 && !vis[dx][dy]) {
                    q.push({dx, dy});
                    vis[dx][dy] = true; // 标记为已访问
                }
            }
        }

        tt++; // 时间增加
        
    }

    // 如果队列为空，说明没有找到安全路径
    cout << "-1" << endl;
}

int main(){
    cin>>m;
    for(int i=1;i<=m;++i){
        cin>>star[i].x>>star[i].y>>star[i].t;
        fuzhu[star[i].x][star[i].y]=1;
        fuzhu[star[i].x-1][star[i].y]=1;//辅助数组为0的地方是永远安全的 
        fuzhu[star[i].x+1][star[i].y]=1;
        fuzhu[star[i].x][star[i].y-1]=1;
        fuzhu[star[i].x][star[i].y+1]=1;
    }
    sort(star+1,star+1+m,compare);
    bfs(0,0,0);
    return 0;
}