#include <iostream>
#include <queue>
using namespace std;

int M;
bool v[1145][1145];
class meteor
{
public:
    int x;
    int y;
    int t;
} star[50010];

class point
{
public:
    int x;
    int y;
    int step;
};

queue<point> r;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool check(int x, int y)
{
    for (int i = 1; i <= M; i++)
    {
        if (((star[i].x == x && star[i].y == y) || (star[i].x + dx[0] == x && star[i].y + dy[0] == y) || (star[i].x + dx[1] == x && star[i].y + dy[1] == y) || (star[i].x + dx[2] == x && star[i].y + dy[2] == y) || (star[i].x + dx[3] == x && star[i].y + dy[3] == y)) || (x < 0 || y < 0))
        {
            return false;
        }
    }
    return true;
}

int main()
{
    cin >> M;
    for (int i = 1; i <= M; i++)
    {
        cin >> star[i].x >> star[i].y >> star[i].t;
    }

    point start;
    start.x = 0;
    start.y = 0;
    start.step = 0;
    r.push(start);
    v[0][0] = 1;
    bool flag = 0;
    while (!r.empty())
    {
        for (int i = 1; i <= M; i++)
        {
            if (star[i].t == r.front().step)
            {
                v[star[i].x][star[i].y] = 1;
                v[star[i].x + dx[0]][star[i].y + dy[0]] = 1;
                v[star[i].x + dx[1]][star[i].y + dy[1]] = 1;
                if (star[i].x + dx[2] >= 0 && star[i].x + dx[2] <= 1144 && star[i].y + dy[2] >= 0 && star[i].y + dy[2] <= 1144)
                    v[star[i].x + dx[2]][star[i].y + dy[2]] = 1;

                if (star[i].x + dx[3] >= 0 && star[i].x + dx[3] <= 1144 && star[i].y + dy[3] >= 0 && star[i].y + dy[3] <= 1144)
                    v[star[i].x + dx[3]][star[i].y + dy[3]] = 1;
            }
        }
        int x = r.front().x;
        int y = r.front().y;
        if (check(x, y))
        {
            flag = 1;
            cout << r.front().step;
            break;
        }
        for (int k = 0; k <= 3; k++)
        {
            int tx, ty;
            tx = x + dx[k];
            ty = y + dy[k];
            if (v[tx][ty] != 1 && tx >= 0 && tx <= 1144 && ty >= 0 && ty <= 1144)
            {
                point temp;
                temp.x = tx;
                temp.y = ty;
                temp.step = r.front().step + 1;
                r.push(temp);
                v[tx][ty] = 1;
            }
        }
        r.pop();
    }

    if (!flag)
    {
        cout << -1;
    }

    return 0;
}