/*
ID: cmykrgb1
PROG: meteor
LANG: C++
*/

#include <iostream>
#define MAX 302
#define MAXT 50001
using namespace std;

typedef struct
{
	int x,y,t;
}star;

class tQueue
{
public:
	class linklist
	{
	public:
		linklist* next;
		star value;
		linklist()
		{
			next=0;
		}
	};
	linklist *first,*last;
	bool used[MAX][MAX];
	int size;
	void add(star p)
	{
		if (size==0)
			first=last=new linklist;
		else
			last=last->next=new linklist;
		last->value=p;
		size++;
		used[p.x][p.y]=true;
	}
	star del()
	{
		star rtn=first->value;
		linklist *tfirst=first;
		first=first->next;
		delete tfirst;
		size--;
		used[rtn.x][rtn.y]=false;
		return rtn;
	}
	void reset()
	{
		size=0;
		first=last=0;
		memset(used,0,sizeof(used));
	}
	tQueue()
	{
		reset();
	}
};

star S[MAXT];
bool Die[MAX][MAX];
bool Map[MAX][MAX];
bool F[MAX][MAX];
int N;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
tQueue Q;

inline int cmp(const void *a,const void *b)
{
	return ((star *)a)->t - ((star *)b)->t;
}

inline bool inrange(int x,int y)
{
	return x>=0 && x<MAX && y>=0 && y<MAX;
}

void put(int i,bool M[][MAX])
{
	if (i==0)return;
	int x=S[i].x,y=S[i].y;
	if (inrange(x,y))
		M[x][y]=true;
	if (inrange(x+1,y))
		M[x+1][y]=true;
	if (inrange(x-1,y))
		M[x-1][y]=true;
	if (inrange(x,y+1))
		M[x][y+1]=true;
	if (inrange(x,y-1))
		M[x][y-1]=true;
}

void init()
{
	int i;
	freopen("meteor.in","r",stdin);
	freopen("meteor.out","w",stdout);
	cin >> N;
	for (i=1;i<=N;i++)
	{
		cin >> S[i].x >> S[i].y >> S[i].t;
		put(i,Die);
	}
	qsort(S+1,N,sizeof(S[0]),cmp);
	S[N+1].t=S[N].t+1;
}

int bfs()
{
	int i,j=0,T;
	star F,Y;
	F.x=F.y=F.t=0;
	Q.add(F);
	while (Q.size)
	{
		F=Q.del();
		if (!Die[F.x][F.y])
			return F.t;
		Y.t=F.t+1;
		if (Y.t>S[j].t)
		{
			while (Y.t>S[j].t)
				put(j++,Map);
		}
		if (Map[F.x][F.y])
			continue;
		for (i=0;i<4;i++)
		{
			Y.x=F.x+dx[i];
			Y.y=F.y+dy[i];
			if (inrange(Y.x,Y.y) && !Map[Y.x][Y.y] && !Q.used[Y.x][Y.y])
			{
				Q.add(Y);
			}
		}
	}
	return -1;
}

int main()
{
	int Ans;
	init();
	Ans=bfs();
	cout << Ans << endl;
	return 0;
}