#include <bits/stdc++.h>
using namespace std;

struct node {
	int x, y, time;
} p;
int m, x, y, t, nx, ny, ti[305][305], b[305][305];


int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
queue<node>q;
int main() {
	cin >> m;
	for (int i = 0; i <= 309; i++)
		for (int j = 0; j <= 309; j++)
			ti[i][j] = -1;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y >> t;
		if (t < ti[x][y] || ti[x][y] == -1)
			ti[x][y] = t;
		for (int i = 0; i < 4; i++) {
			nx = x + dx[i];
			ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && (ti[nx][ny] == -1 || t < ti[nx][ny]))
				ti[nx][ny] = t;
		}
	}
	p.x = 0, p.y = 0, p.time = 0, b[0][0] = 1;
	q.push(p);
	while (!q.empty()) {
		p = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			nx = p.x + dx[i], ny = p.y + dy[i];
			if (nx >= 0 && ny >= 0 && b[nx][ny] == 0 && (ti[nx][ny] == -1 || p.time + 1 < ti[nx][ny])) {
				node tx;
				tx.x = nx, tx.y = ny, tx.time = p.time + 1, b[nx][ny] = 1;
				q.push(tx);
				if (ti[nx][ny] == -1) {
					cout << tx.time << endl;
					return 0;
				}
			}
		}
	}
	cout << -1 << endl;
	return 0;
}