#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Node
{
    int x, y, t;
};
int m, x, y, t, vist[305][305];
int dir[5][2]{{0, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
queue<Node> a;
int main()
{
    cin >> m;
    memset(vist, 0x3f, sizeof(vist));
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> t;
        for (int j = 0; j < 5; j++)
        {
            if (vist[x + dir[j][0]][y + dir[j][1]] > t)
            {
                vist[x + dir[j][0]][y + dir[j][1]] = t;
            }
        }
    }
    a.push(Node{0, 0, 0});
    while (!a.empty())
    {
        Node tmp = a.front();
        if (vist[tmp.x][tmp.y] == 0x3f3f3f3f)
        {
            cout << tmp.t;
            return 0;
        }
        vist[tmp.x][tmp.y] = -1;
        for (int i = 1; i <= 4; i++)
        {
            x = tmp.x + dir[i][0];
            y = tmp.y + dir[i][1];
            if (x >= 0 && y >= 0 && x <= 303 && y <= 303 && vist[x][y] > tmp.t + 1)
            {
                a.push(Node{tmp.x + dir[i][0], tmp.y + dir[i][1], tmp.t + 1});
            }
        }
        a.pop();
    }
    cout << -1;
    return 0;
}