#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
int safe[500][500];
int t[1005], x[1005], y[1005];
bool vis[500][500];
int d1[4] = { 0,0,1,-1 };
int d2[4] = { 1,-1,0,0 };
struct node 
{
	int time, x, y;
};
queue<node> q;
int main()
{
	int m;
	cin >> m;
	for (int i = 0; i <= 305; i++)
		for (int j = 0; j <= 305; j++)
		{
			safe[i][j] = 1e9;
		}
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &x[i], &y[i], &t[i]);
		if (t[i] < safe[x[i]][y[i]])
			safe[x[i]][y[i]] = t[i];
		for (int j = 0; j < 4; j++)
		{
			int nx = x[i] + d1[j];
			int ny = y[i] + d2[j];
			if (nx >= 0 && ny >= 0 && safe[nx][ny] > t[i])
			{
				safe[nx][ny] = t[i];
			}
		}
	}
	//for (int i = 0; i <= 10; i++)
	//{
	//	for (int j = 0; j <= 10; j++)
	//	{

	//		printf("%4d ", safe[i][j]);
	//	}
	//	putchar('\n');
	//}
	vis[0][0] = 1;
	q.push(node{ 0,0,0 });
	while (!q.empty())
	{
		node r = q.front(); 
		q.pop();
	//	printf("%d %d %d\n", r.time, r.x, r.y);
		for (int j = 0; j < 4; j++)
		{
			int nx = r.x + d1[j], ny = r.y + d2[j];
			//if (r.time >= safe[nx][ny]) printf("??");
			if (nx < 0 || ny < 0 || (r.time+1 >= safe[nx][ny]) || vis[nx][ny] == 1) continue;
			//printf("dwq");
			vis[nx][ny]=1;
			q.push(node{ r.time + 1,nx,ny });
			if (safe[nx][ny] == 1e9)
			{
			//	cout << nx << ' ' << ny << ' ';
				cout << r.time + 1;
				return 0;
			}
		}
	}
	printf("-1");
	return 0;
}