#include<bits/stdc++.h>
#define maxn 0x3f3f3f3f
using namespace std;

int b[500][500];
int c[500][500];
int dir[10][10] = { {0,0},{0,1},{1,0},{-1,0},{0,-1} };

struct node
{
	int x;
	int y;
	int t;
};

int main()
{
	freopen("ans.txt", "r", stdin);

	int m;
	cin >> m;

	for (int i = 0; i <= 500; i++)
	{
		for (int j = 0; j <= 500; j++)
		{
			b[i][j] = maxn;
		}
	}//预处理时间数组

	while (m--)
	{
		int x, y, t;
		cin >> x >> y >> t;

		for (int i = 0; i <= 4; i++)
		{
			int tx = x + dir[i][0];
			int ty = y + dir[i][1];
			
			if (tx < 0 || ty < 0 || b[tx][ty] != maxn)
			{
				continue;
			}
			
			b[tx][ty] = t;
		}
	}//预处理陨石坑

	queue<node>s;
	s.push({ 0,0,0 });
	while (!s.empty())
	{
		node first = s.front();
		s.pop();

		for (int i = 1; i <= 4; i++)
		{
			int tt = first.t + 1;
			int tx = first.x + dir[i][0];
			int ty = first.y + dir[i][1];

			if (tx < 0 || ty < 0 || tt>=b[tx][ty]||c[tx][ty]==1)
			{
				continue;
			}

			if (b[tx][ty] == maxn)
			{
				cout << tt;
				return 0;
			}
			c[tx][ty] = 1;
			s.push({ tx,ty,tt });
		}
	}
	cout << "-1";
	return 0;
}