#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;
struct rec{
	int x,y,s;
};
queue<rec>q;
int n;
int a[310][310];
bool vis[310][310];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int ans;
int a1[50010],b1[50010],c1[50010];
void bfs(){
	rec v;
	v.x=0;
	v.y=0;
	v.s=0;
	q.push(v);
	for (int i=1;i<=n;i++){
		if (c1[i]==0){
			a[a1[i]][b1[i]]=1;
			for (int j=0;j<=3;j++){
				int xx=a1[i]+dx[j];
				int yy=b1[i]+dy[j];
				if (xx>=0&&yy>=0&&xx<=300&&yy<=300){
					a[xx][yy]=1;
				}
			}
		}
	}
	if (a[0][0]==1){
		ans=-1;
		return ;
	}
	while (q.size()!=0){
		int f=0;
		v=q.front();
		q.pop();
		int x=v.x;
		int y=v.y;
		int s=v.s;
		vis[x][y]=true;
		for (int i=1;i<=n;i++){
			if (x==a1[i]&&y==b1[i]){
				f=1;
				break;
			}
			for (int j=0;j<4;j++){
				int xx=a1[i]+dx[j];
				int yy=b1[i]+dy[j];
				if (xx>=0&&yy>=0&&xx<=300&&yy<=300){
					if (x==xx&&y==yy){
						f=1;
						break;
					}
				}
			}
			if (f==1) break;
		}
		if (f==0){
			ans=min(ans,s);
		}
		for (int i=1;i<=n;i++){
			if (c1[i]==s+1){
				a[a1[i]][b1[i]]=1;
				for (int j=0;j<=3;j++){
					int xx=a1[i]+dx[j];
					int yy=b1[i]+dy[j];
					if (xx>=0&&yy>=0&&xx<=300&&yy<=300){
						a[xx][yy]=1;
					}
				}
			}
		}
		for (int i=0;i<=3;i++){
			int xx=dx[i]+x;
			int yy=dy[i]+y;
			if (xx>=0&&yy>=0&&xx<=300&&yy<=300&&vis[xx][yy]==false&&a[xx][yy]==0){
				v.x=xx;
				v.y=yy;
				v.s=s+1;
				vis[xx][yy]=true;
				q.push(v);
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	ans=9999999;
	for (int i=1;i<=n;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		a1[i]=x;
		b1[i]=y;
		c1[i]=z;
	}
	bfs();
	printf("%d",ans);
	return 0;
}