#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
#define M 305
int n, map[M][M], ans = 0x7fffffff;
bool vis[M][M];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int bfs(int xx, int yy, int tt)
{
if (map[xx][yy] == -1)
{
ans = min(tt, ans);
return ans;
}
for (int i = 0; i < 4; i++)
{
int nx = xx + dx[i], ny = yy + dy[i];
if (nx >= 0 && ny >= 0 && !vis[nx][ny] && (map[nx][ny] > tt + 1 || map[nx][ny] == -1))
{
//vis[nx][ny] = true; 添加这行能解决tle问题但是会wa一半的样例
bfs(nx, ny, tt + 1);
}
}
}
int main()
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> n;
int sx, sy, st;
for (int i = 0; i < 305; i++)
for (int j = 0; j < 305; j++)
map[i][j] = -1;
for (int i = 1; i <= n; i++)
{
cin >> sx >> sy >> st;
if (st <= map[sx][sy] || map[sx][sy] == -1)
map[sx][sy] = st;
for (int k = 0; k < 4; k++)
{
if (sx + dx[k] >= 0 && sy + dy[k] >= 0)
if (st <= map[sx + dx[k]][sy + dy[k]] || map[sx + dx[k]][sy + dy[k]] == -1)
map[sx + dx[k]][sy + dy[k]] = st;
}
}
vis[0][0] = true;
bfs(0, 0, 0);
if (ans != 0x7fffffff)
cout << ans << endl;
else
cout << "-1" << endl;
return 0;
}```