#include <stdio.h>

#include <memory.h>

#include <queue>

using namespace std;

#define MAX 302        ///地图宽度

int m;    ///流星数

int map[MAX][MAX];    ///地图

bool visited[MAX][MAX];    ///是否访问过

int last;    ///最晚的流星时间

int go[][] ={{,},{-,},{,},{,-},{,}}; ///五个方向

struct Meteor

{

    int x;

    int y;

    int t;

}meteor[];    ///流星结构

typedef Meteor Node;    ///节点结构，用于bfs

int max(int a, int b)

{

    return a > b ? a : b;

}

int bfs()

{

    memset(visited, false, sizeof(visited));

    queue<Node> q;    ///队列

    Node fir;    ///起始点入队

    fir.x = fir.y = fir.t = ;

    visited[][] = true;

    q.push(fir);

    while (!q.empty())    ///bfs

    {

        Node now = q.front();

        q.pop();

        for (int i = ; i < ; i++)    ///每次必须行动1格

        {

            Node tmp = now;

            tmp.x += go[i][];

            tmp.y += go[i][];

            tmp.t++;

            if (tmp.x >=  && tmp.y >=  && map[tmp.x][tmp.y]>tmp.t && !visited[tmp.x][tmp.y])    ///没越界、流星还未砸这个格子、还没访问过(重复访问就是不是bfs最优解了)

            {

                visited[tmp.x][tmp.y] = true;    ///标记

                if (map[tmp.x][tmp.y] > last)    ///如果格子不会被砸到

                {

                    return tmp.t;

                }

                q.push(tmp);

            }

        }

    }

    return -;

}

int main()

{

    while (scanf("%d", &m) != EOF)

    {

        for (int i = ; i < m; i++)

        {

            scanf("%d%d%d", &meteor[i].x, &meteor[i].y, &meteor[i].t);

        }

        memset(map, 0x7f, sizeof(map));    ///要严谨一点可以用0x7fffffff，不过就不能用memset了

        for (int i = ; i < m; i++)

        {

            ///计算最晚流星的时间

            if (i == )

                last = meteor[i].t;

            else

                last = max(last, meteor[i].t);

            ///更新地图上某个点的最快的流星下落时间

            for (int j = ; j < ; j++)

            {

                int tx = meteor[i].x + go[j][];

                int ty = meteor[i].y + go[j][];

                if (tx >=  && ty >=  && map[tx][ty]>meteor[i].t)

                {

                    map[tx][ty] = meteor[i].t;

                }

            }

        }

        if (map[][] == )    ///起始点被砸直接gg

            printf("-1\n");

        else  ///否则bfs

            printf("%d\n", bfs());

    }

    return ;

}