#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
int dirx[5]={0,0,0,-1,1};
int diry[5]={0,-1,1,0,0};
typedef pair<int ,int >pii;
queue<pii>q;
int m;
int s[302][302];
int t[302][302];


int bfs()
{
	q.push({0,0});
	int sx,sy,xx,yy;
	
	while (!q.empty())
	{
		pii tx=q.front();
		q.pop();
		sx=tx.x;
		sy=tx.y;
		
		for(int i=1;i<5;i++){
			xx=sx+dirx[i];
			yy=sy+diry[i];
			if(xx<0||xx>300||yy<0||yy>300)continue;
			
			if(!t[xx][yy])
			{
				t[xx][yy]=t[sx][sy]+1;
				if(s[xx][yy]==0) return t[xx][yy];
				else if(t[xx][yy]<s[xx][yy])q.push({xx,yy});
			}
			
		}
	}
	return -1;
}

int main()
{
	cin>>m;
	int aa,bb,jj;
	int i,j;
	for(int k=1;k<=m;k++)
	{
		cin>>i>>j>>jj;
		if(jj==0)jj=-1;
		
		
		for(int op=0;op<5;op++){
			aa=i+dirx[op];
			bb=j+diry[op];
			if(aa<0||aa>300||bb<0||bb>300)continue;
			
			if(s[aa][bb]==0)s[aa][bb]=jj;
			else s[aa][bb]=min(s[aa][bb],jj);
			
	}
		
	}
	cout<<bfs();
	
}