#include<bits/stdc++.h>
using namespace std;
const int numn=310;
int a[numn][numn];
bool bo[numn][numn];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int findtime(){
    int ans=0;if(a[0][0]==INT_MAX)return 0;
    queue<pair<int,int>> q;
    q.push({0,0});
    bo[0][0]=true;
    while ((!q.empty()))
    {   
        int size=q.size();
        while(size--){
            pair<int,int>temp=q.front();

            q.pop();
            for(int i=0;i<4;i++){
                int nx=temp.first+dx[i];
                int ny=temp.second+dy[i];
                if(nx>-1&&ny>-1&&ans+1<a[nx][ny]&&nx<=300&&ny<=300&&!bo[nx][ny]){
                    if(a[nx][ny]==99999||nx>300||ny>300)return ans+1;
                    q.push({nx,ny});
                    bo[nx][ny]=true;
                }
            }
        }
        ans++;
    }
    return -1;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i = 0; i <= 310; i++) {
    for(int j = 0; j <= 310; j++) {
        a[i][j] = 99999;
    }
}
    memset(bo,0,sizeof(bo));
    for(int i=0;i<n;i++){
        int d,b,c;
        cin>>d>>b>>c;
        a[d][b]=min(a[d][b],c);
        if(d>0)a[d-1][b]=min(a[d-1][b],c);
        if(b>0)a[d][b-1]=min(a[d][b-1],c);
        a[d+1][b]=min(a[d+1][b],c);
        a[d][b+1]=min(c,a[d][b+1]);
    }
    cout<<findtime()<<endl;

}