#include <iostream>
#include <algorithm>
#include <queue>
#include <stdio.h>
using namespace std;
const int MAX = 305;
// 初始流行掉落的时间
int inf = 1 << 30;
int dp[MAX][MAX];
// 控制方向
int dx[] = {0, 1, 0, -1, 0};
int dy[] = {1, 0, -1, 0, 0};
struct node
{int x, y, t;
};
int BFS()
{queue<node> q;// 可能(0,0) 点爆炸时间是0if (dp[0][0] > 0)q.push((node){0, 0, 0});while (!q.empty()){node t = q.front();q.pop();// 如果发现了一个可以不被爆炸的地方if (dp[t.x][t.y] == inf)return t.t;// 扫描临点for (int i = 0; i < 4; i++){int nx = t.x + dx[i];int ny = t.y + dy[i];// t.t+1 是因为走过去也得花时间// t.t是当前已经花的时间if (nx >= 0 && ny >= 0 && t.t + 1 < dp[nx][ny]){// 防止在回去if (dp[nx][ny] != inf)dp[nx][ny] = t.t + 1;q.push((node){nx, ny, t.t + 1});}}}return -1;
}int main()
{int N;cin >> N;// 这才知道原来二维的也能用fill fill(dp[0], dp[0] + MAX * MAX, inf);while (N--){int x, y, t;scanf("%d%d%d", &x, &y, &t);// 修改与他相邻的点的爆炸时间for (int i = 0; i < 5; i++){int nx = x + dx[i];int ny = y + dy[i];// 等于最小的爆炸时间if (nx >= 0 && ny >= 0){dp[nx][ny] = min(dp[nx][ny], t);}}}cout << BFS();return 0;
}