// I'm gagapuma
// Problem: P2895 [USACO08FEB]Meteor Shower S
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2895
// Memory Limit: 125 MB
// Time Limit: 1000 ms


#include <bits/stdc++.h>
using namespace std;
//#define MAXN 100010
#define rep(i,a,n) for (int i=a;i<=n;++i)
#define per(i,a,n) for (int i=n;i>=a;--i)
#define rep0(i,n) for(int i=0;i<n;++i)
#define INF 1000000000
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pob pop_back
#define all(x) (x).begin(),(x).end()
#define ent putchar('\n')
#define sp putchar(' ')
//const int N = ;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
inline void write(int x){ 
    if(x==0){putchar('0');return;}
	int len=0,k1=x,c[10005];
	if(k1<0)k1=-k1,putchar('-');
	while(k1)c[len++]=k1%10+'0',k1/=10;
	while(len--)putchar(c[len]);
}
inline void write(ll x){ 
    if(x==0){putchar('0');return;}
	int len=0,k1=x,c[10005];
	if(k1<0)k1=-k1,putchar('-');
	while(k1)c[len++]=k1%10+'0',k1/=10;
	while(len--)putchar(c[len]);
}
inline void read(int &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
inline void read(ll &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
#define N 800

struct node
{
	int x,y,t;
};

int dx[10]={1,0,0,-1};
int dy[10]={0,1,-1,0};
int t[N][N];
bool st[N][N];
int m;
node q[N*N];

int bfs()
{
	int hh=0,tt=-1;
	q[++tt]={0,0,0};
	st[0][0]=1;
	while(hh<=tt)
	{
		node p=q[++hh];
		rep0(i,4)
		{
			int tx=p.x+dx[i],ty=p.y+dy[i];
			if(tx>-1 && ty>-1 && st[tx][ty]==0 && (t[tx][ty]==-1 || p.t+1<t[tx][ty]) )
			{
				st[tx][ty]=1;
				q[++tt]={tx,ty,p.t+1};
				if(t[tx][ty]==-1)
				{
					return p.t+1;
				}
			}
		}
	}

	return -1;
}

int main()
{
	memset(t,-1,sizeof t);
	read(m);
	rep(i,1,m)
	{
		int x,ti,y;
		read(x),read(y),read(ti);
		if(ti<t[x][y] || t[x][y]==-1)
			t[x][y]=ti;
		rep0(j,4)
		{
			int tx=x+dx[j],ty=y+dy[j];
			if(tx>-1 && ty>-1 && (t[tx][ty]==-1 || ti<t[tx][ty]) )
				t[tx][ty]=ti;
		}
	}

	
	printf("%d",bfs());

	
	return 0;
}