#include <cstdio>

#include <string>

#include <cstdlib>

#include <cmath>

#include <iostream>

#include <cstring>

#include <set>

#include <queue>

#include <algorithm>

#include <vector>

#include <map>

using namespace std ;

typedef long long LL;

typedef pair<int, int> P;

const int INF = 0x3f3f3f3f;

const double inf = 0x3f3f3f3f3f3f3f;

const double eps = 1e-8;

const int maxn = 300 + 15;

const int dr[] = {0, 0, -1, 1};

const int dc[] = {-1, 1, 0, 0};

int m, n;

inline bool is_in(int r, int c){

    return r >= 0 && r < n && c >= 0 && c < m;

}

int s[maxn][maxn];

int vis[maxn][maxn];

struct node{

    int x, y, d;

    node(int xx, int yy, int dd) : x(xx), y(yy), d(dd) { }

};

int bfs(){

    queue<node> q;

    q.push(node(0, 0, 0));

    vis[0][0] = 1;

    if(!s[0][0])  return -1;

    while(!q.empty()){

        node u = q.front();  q.pop();

        for(int i = 0; i < 4; ++i){

            int x = u.x + dr[i];

            int y = u.y + dc[i];

            if(x < 0 || y < 0 || x > 305 || y > 305 || vis[x][y] || s[x][y] <= u.d+1)  continue;

            vis[x][y] = 1;

            if(s[x][y] == INF)  return u.d+1;

            q.push(node(x, y, u.d+1));

        }

    }

    return -1;

}

int main(){

    while(scanf("%d", &n) == 1){

        int x, y, t;

        for(int i = 0; i < 305; ++i)

            for(int j = 0; j < 305; ++j)

                s[i][j] = INF;

        for(int i = 0; i < n; ++i){

            scanf("%d %d %d", &x, &y, &t);

            if(x > 0)  s[x-1][y] = min(t, s[x-1][y]);

            if(y > 0)  s[x][y-1] = min(t, s[x][y-1]);

            s[x+1][y] = min(t, s[x+1][y]);

            s[x][y+1] = min(t, s[x][y+1]);

            s[x][y] = min(t, s[x][y]);

        }

        memset(vis, 0, sizeof(vis));

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

    }

    return 0;

}