#include <bits/stdc++.h>
using namespace std;
int dx[4] = {1,0,-1,0},dy[4]= {0,1,0,-1};
int t[305][305];
bool vis[305][305];
bool flag[305][305];
int m;
struct point{int x;int y;int time;};
int bfs(int x,int y,int time){
	queue<point>q;q.push({x,y,time});
	while(!q.empty()){
		point now = q.front();q.pop();
		if (vis[now.x][now.y] == 1){
			return now.time;
		}
		for (int i = 0;i<4;i++){
			int nx = now.x+dx[i],ny = now.y+dy[i];
			if (nx<0 || ny<0 || nx>300|| ny>300) continue;
			if (t[nx][ny]>now.time+1&&flag[nx][ny] == 0){
				flag[nx][ny] = 1;
				q.push({nx,ny,now.time+1});
			}
		}
	}
	return -1;
}
void bj(int x,int y,int time){
	vis[x][y] = 0;t[x][y] = time;
	for (int i = 0;i<4;i++){
		if (x+dx[i]<0 || y+dy[i]<0 ) continue;
		vis[x+dx[i]][y+dy[i]] = 0;
		t[x+dx[i]][y+dy[i]] = time;
	}
}
signed main(){
	memset(flag,0,sizeof(flag));
	memset(t,0x3f,sizeof(t));
	memset(vis,1,sizeof(vis));
	cin>>m;
	for (int i = 1;i<=m;i++){
		int x,y,time;cin>>x>>y>>time;
		time = min(time,t[x][y]);
		bj(x,y,time);
	}
	cout<<bfs(0,0,0);
	return 0;
}
/*
23
2 5 10
1 3 5
5 3 12
3 3 9
1 8 7
8 4 15
2 3 7
0 0 2
6 7 10
4 4 10
3 7 7
8 5 13
0 4 9
2 6 8
0 2 4
6 4 12
0 6 7
4 2 10
1 4 7
4 6 10
5 5 12
6 5 14
2 1 2

13
*/