#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 300 + 10;
const int INF = 0x3f3f3f3f;
struct node
{
	int x , y , time;
};
struct zha
{
	int x , y , t;
}a [50000];
bool v [1010];
int dx [] = {1 , -1 , 0 , 0};
int dy [] = {0 , 0 , 1 , -1};
queue < node > q;
int M , sx , sy , sz , cnt = 1 , n;
bool k [N] [N] , l [N] [N];
bool check (int x , int y)
{
	if (x >= 0 && y >= 0 && !k [x] [y] )
	    return 1;
	return 0;
}
bool cmp (zha x1 , zha x2)
{
	return x1.t < x2.t;
}
void boom (int time)
{
	v [time] = 1; 
	for (int i = cnt; i <= n; i++)
	{
		if (a [i].t <= time)
	    {
	    	cnt++;
	    	k [a [i].x] [a [i].y] = 1;
			for (int j = 0; j <= 3; j++)
	    	{
	    		int xx = a [i].x + dx [j];
	    		int yy = a [i].y + dy [j];
	    		if (check (xx , yy))
	    		{
	    			k [xx] [yy] = 1;
				}
			}
		}
		else return;
	}
	    
}
void bfs ()
{
	v [0] = 1;
	k [0] [0] = 1;
	q.push ( (node) {0 , 0 , 0});
	while ( !q.empty() )
	{
		node top = q.front();
		q.pop();
		if (!v [top.time + 1]) boom (top.time + 1);
		if (!l [top.x] [top.y])
		{
			cout << top.time;
			exit (0);
		} 
	    for (int j = 0; j <= 3; j++)
	    {
	    	int xx = top.x + dx [j];
	    	int yy = top.y + dy [j];
	    	if (check (xx , yy))
	    	{
	    		q.push ( (node) {xx , yy , top.time + 1});
				k [xx] [yy] = 1;
			}
		}
	}
	cout << -1;
}
int main()
{
	    cin >> n;
	    for (int i = 1; i <= n; i++)
	    {
	    	cin >> a [i].x >> a [i].y >> a [i].t;
	    	l [a [i].x] [a [i].y] = 1;
	    	for (int j = 0; j <= 3; j++)
	    	{
				int xx = a [i].x + dx [j];
	    		int yy = a [i].y + dy [j];
	    		if (check (xx , yy))
	    		{
	    			l [xx] [yy] = 1;
				}
				
			}
		}
	    sort (a + 1 , a + n + 1 , cmp);
	    boom(0);
		bfs ();
		return 0;
}