#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;
typedef long long ll;
typedef pair <int, int> PII;
const int N = 500;

int d[N][N], g[N][N]; // 距离 地图的距离点
int ans[N][N];
int n;
int dx[4] = {0, 1, -1, 0}, dy[4] = {1, 0, 0, -1};

struct stu
{
    int t, x , y;
    int num;
}p[N];

bool cmp(stu a, stu b)   // 排序用
{
    if(a.t != b.t)
        return a.t < b.t;
    return a.num < b.num;
}

void dispose()
{
    memset(g, -1, sizeof -1);
    for (int i = 1;i <= n;i ++ )
    {
        g[p[i].x][p[i].y] = p[i].t;
        for (int j = 0; j < 4; j++)
        {
            int x = p[i].x + dx[j], y = p[i].y + dy[j];
            if(x >= 0 && x <= 300 && y >= 0 && y <= 300 && g[x][y] == 0)
                g[x][y] = p[i].t + 1;
        }
    }
}

void bfs()
{
    queue <PII> q;
    q.push({0, 0});

    memset(d, -1, sizeof d);
    d[0][0] = 0;
    g[0][0] = 1;
    ans[0][0] = 1;
    while(q.size() )
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4;i ++ )
        {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x >= 0 && x <= 500 && y >= 0 && y <= 500 && d[x][y] == -1 && (d[t.first][t.second] + 1 < g[x][y] - 1 || g[x][y] == 0) && ans[x][y] == 0)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x, y});
                ans[x][y] = 1;
                if(g[x][y] == 0)
                {
                    cout << d[x][y] << endl;
                    return;
                }
            }
        }
    }
    cout << -1 << endl;
    return;
}

void solve()
{
    cin >> n;
    for (int i = 1;i <= n;i ++ )
        cin >> p[i].x >> p[i].y >> p[i].t, p[i].num = i;
    sort(p + 1, p + 1 + n, cmp);
    dispose();
    bfs();
}

int main()
{
    solve();
    return 0;
}