#include<bits/stdc++.h>
using namespace std;
int mp[310][310] = {0}, np[50001][3], ans = 999999999;
bool mmp[310][310] = {false};
void dfs(int x, int y, int cnt) {
	if (x >= 301 || y >= 301 || x < 0 || y < 0)return;
	if (mp[x][y] <= cnt)return;
	if (mp[x][y] == 99999999) {
		ans = min(ans, cnt);
		return;
	}
	mmp[x][y] = true;
	dfs(x, y + 1, cnt + 1);
	dfs(x, y - 1, cnt + 1);
	dfs(x + 1, y, cnt + 1);
	dfs(x - 1, y, cnt + 1);
// 	mmp[x][y] = false;
}
int main() {
	int m;
	cin >> m;
	fill(mp[0], mp[0] + 310 * 310, 99999999);
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d",&np[i][0],&np[i][1],&np[i][2]);
		mp[np[i][0]][np[i][1]] = min(mp[np[i][0]][np[i][1]], np[i][2]);
		mp[np[i][0] + 1][np[i][1]] = min(np[i][2], mp[np[i][0] + 1][np[i][1]]);
		if (np[i][0] - 1 >= 0)
			mp[np[i][0] - 1][np[i][1]] = min(np[i][2], mp[np[i][0] - 1][np[i][1]]);
		mp[np[i][0]][np[i][1] + 1] = min(np[i][2], mp[np[i][0]][np[i][1] + 1]);
		if (np[i][1] - 1 >= 0)
			mp[np[i][0]][np[i][1] - 1] = min(np[i][2], mp[np[i][0]][np[i][1] - 1]);
	}
//	for (int i = 0; i < 20; i++) {
//		for (int j = 0; j < 20; j++) {
//			if (mp[i][j] == 99)cout << 0 << ' ';
//			else cout << mp[i][j] << ' ';
//		}
//		cout << endl;
//	}
	dfs(0, 0, 0);
	if (ans == 999999999)cout << -1;
	else cout << ans << endl;
	return 0;
}