#include <bits/stdc++.h>
using namespace std;
int m,ans,t;
int step[5000][5000];
int mapp[5000][5000];
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
typedef pair<int,int> P;

queue <P> q;

struct star
{
	int x;
	int y;
	int t;
}stf[100000];



void bfs(int i,int j)
{
	q.push(P(i,j));
	if(mapp[i][j]==1)
	{
		return;
	}
	while(q.size())
	{
		int x=q.front().first;
		int y=q.front().second;
		q.pop();
		int flag=0;
		for(int k=1;k<=4;k++)
		{
			int nx=x+dx[k];
			int ny=y+dy[k];
			
			if(!flag)
			{
				for(int k=1;k<=m;k++)
				{
					if(step[x][y]==stf[k].t)
					{
						mapp[stf[k].x][stf[k].y]=2;
						for(int u=1;u<=4;u++)
						{
							int ex=stf[k].x+dx[u];
							int ey=stf[k].y+dy[u];
							if(ex<0||ex>300||ey<0||ey>300) continue;
							mapp[ex][ey]=2;
						}
					}
					flag=1;
				}				
			}	
					
			if(nx<0||nx>300||ny<0||ny>300||step[nx][ny]||mapp[nx][ny]==2) continue;

			step[nx][ny]=step[x][y]+1;
			
			q.push(P(nx,ny));
			if(mapp[nx][ny]==1)
			{
				ans=step[nx][ny];
				return;
			}
		}
	}
}

int main()
{
	step[0][0]=1;
	cin>>m;
	
	for(int i=0;i<m;i++)
	{
		cin>>stf[i].x>>stf[i].y>>stf[i].t;
		if(stf[i].t==0)
		{
			mapp[stf[i].x][stf[i].y]=2;
			for(int u=1;u<=4;u++)
			{
				int ex=stf[u].x+dx[u];
				int ey=stf[u].y+dy[u];
				if(ex<0||ex>300||ey<0||ey>300) continue;
				mapp[ex][ey]=2;	
			}			
		}
	}
	
	int flag=0;
	
	for(int i=0;i<=300;i++)
	{
		for(int j=0;j<=300;j++)
		{
			for(int k=0;k<m;k++)
			{
				if((i==stf[k].x&&j==stf[k].y)||(i==stf[k].x&&j==stf[k].y-1)||(i==stf[k].x&&j==stf[k].y+1)||(i==stf[k].x+1&&j==stf[k].y)||(i==stf[k].x-1&&j==stf[k].y))                                      
				{
					flag=1;
					break;
				}
			}
			if(!flag)
			{
				mapp[i][j]=1;
			}
			flag=0;
		}
	}

	bfs(0,0);
	cout<<ans-1;
	
	return 0;
 }