#include<bits/stdc++.h>
using namespace std;
int n,x,y,t,a[305][305],vis[305][305];
struct NODE{
	int x,y,s;
};
queue<NODE> q;
void push(int x,int y,int s)
{
	if(x<0||x>300||y<0||y>300||vis[x][y]||(a[x][y]<=s&&a[x][y]!=0)) return;
	q.push({x,y,s});
	vis[x][y]=1;
}
void bfs()
{
	push(0,0,0);
	while(!q.empty())
	{
		int x=q.front().x,y=q.front().y,s=q.front().s;
		q.pop();
		if(a[x][y]==0)
		{
			cout<<s<<endl;
			return;
		}
		push(x+1,y,s+1);
		push(x-1,y,s+1);
		push(x,y+1,s+1);
		push(x,y-1,s+1);
	}
	cout<<-1<<endl;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>y>>x>>t;
		if(a[x][y]>0) a[x][y]=min(a[x][y],t);
		else a[x][y]=t;
		if(x<300)
		{
			if(a[x][y]>0) a[x+1][y]=min(a[x][y],t);
			else a[x][y]=t;
		}
		if(x>0)
		{
			if(a[x][y]>0) a[x-1][y]=min(a[x][y],t);
			else a[x][y]=t;
		}
		if(y<300)
		{
			if(a[x][y]>0) a[x][y+1]=min(a[x][y],t);
			else a[x][y]=t;
		}
		if(y>0)
		{
			if(a[x][y]>0) a[x][y-1]=min(a[x][y],t);
			else a[x][y]=t;
		}
	}
	bfs();
	return 0;
}