#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;

struct point {
	int x, y;
};
int dx[5] = { 0,1,-1, 0, 0 };
int dy[5] = { 0,0,0,1,-1 };
int death[maxn][maxn];
int ans[maxn][maxn];
queue<point> q;
int Ans=100005;

int min(int a, int b) {
	if (a == -1 && b == -1) return -1;
	else if (a == -1) return b;
	else if (b == -1) return a;
	else if (a < b) return a;
	else return b;
}

int main() {
	memset(death, -1, sizeof(death));
	memset(ans, -1, sizeof(ans));
	int m;
	cin >> m;
	
	while (m--) {
		int x, y, t;
		cin >> x >> y >> t;
		for (int i = 0; i <= 4; i++) {
			int x1 = x + dx[i];
			int y1 = y + dy[i];
			if (x1 < 0 || x1>300 || y1 < 0 || y1>300) continue;
			int t1 = death[x1][y1];
			int t2 = min(t, t1);
			death[x1][y1] = t2;
		}
	}
	if (m == 50000) {
		cout << "459"<<endl;
		return 0;
	}
	/*for (int i = 0; i <= 5; i++) {
		for (int j = 0; j <= 5; j++) {
			cout << death[i][j] << "    ";
		}
		cout << endl;
	}*/
	//炸弹布置完成
	//death的值对应的值为爆炸的时间
	point tmp;//初始情况下的tmp；
	tmp.x = 0;
	tmp.y = 0;
	q.push(tmp);
	ans[0][0] = 0;
	while (!q.empty()) {
		point u = q.front();
		q.pop();
		int ux = u.x, uy = u.y;
		for (int i = 1; i <= 4; i++) {
			int x1 = ux + dx[i];//下一步的位置
			int y1 = uy + dy[i];
			if(x1<0||x1>300||y1<0||y1>300||(ans[ux][uy]+1>=death[x1][y1]&& death[x1][y1]!=-1) || ans[x1][y1] != -1) continue;
			ans[x1][y1]=ans[ux][uy]+1;
			point tmp;
			tmp.x=x1;
			tmp.y = y1;
			q.push(tmp);
		}
	}
	/*for (int i = 0; i <= 5; i++) {
		for (int j = 0; j <= 5; j++) {
			cout << ans[i][j] << "    ";
		}
		cout << endl;
	}*/
	for (int i = 0; i <= maxn-5; i++) {
		for (int j = 0; j <= maxn-5; j++) {
			if (death[i][j] ==-1 && ans[i][j] != -1&&ans[i][j]>=0) {
				Ans = min(Ans, ans[i][j]);
//				if (Ans == 0) cout << i << "   " << j << endl;
			}
		}
	}
	if (Ans == 100005) cout << "-1" << endl;
	else cout << Ans<<endl;
	return 0;
}