#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

struct ll
{
	int x;
	int y;
	int t;
}ys[50005];

struct lll
{
	int x[315];
	int y[315];
	int sum = 0;
}qz[315];

int map[315][315] = { 0 }, n, fx[4] = { -1,1,0,0 }, fy[4] = { 0,0,-1,1 },
x, y, xl, yl, in, ans = 999;

void BFS(int k)
{
	if (qz[k].sum == 0)return;
	if (ys[in].t == -1)return;
	for (int i = 1; i <= qz[k].sum; i++)
	{
		x = qz[k].x[i];
		y = qz[k].y[i];
		if (map[x][y] == -1)continue;
		for (int j = 0; j < 4; j++)
		{
			xl = x + fx[j];
			yl = y + fy[j];
			if (xl < 0)continue;
			if (yl < 0)continue;
			if (map[xl][yl] == 0)
			{
				map[xl][yl] = k + 1;
				qz[k + 1].sum++;
				qz[k + 1].x[qz[k+1].sum] = xl;
				qz[k + 1].y[qz[k + 1].sum] = yl;
			}
		}
	}
	if (ys[in].t == k + 1)
	{
		while (ys[in].t == k + 1)
		{
			x = ys[in].x;
			y = ys[in].y;
			map[x][y] = -1;
			for (int j = 0; j < 4; j++)
			{
				xl = x + fx[j];
				yl = y + fy[j];
				if (xl < 0)continue;
				if (yl < 0)continue;
				map[xl][yl] = -1;
			}
			in++;
		}
	}
	BFS(k + 1);
}

int main()
{
	int max = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> ys[i].x >> ys[i].y >> ys[i].t;
		if (ys[i].t > max)max = ys[i].t;
	}
	ys[n + 1].t = -1;
	qz[0].x[1] = 0;
	qz[0].y[1] = 0;
	qz[0].sum = 1;
	map[0][0] = 999;
	in = 1;
	BFS(0);
	for (int i = 0; i <= max; i++)
	{
		for (int j = 0; j <= max; j++)
		{
			if (map[i][j] <= 0)continue;
			if (map[i][j] < ans)ans = map[i][j];
		}
	}
	if (map[0][0] == 999)ans = 0;
	if (ans == 999)ans = -1;
	cout << ans << endl;
	return 0;
}