def bfs():
    dic=[[-1,0],[1,0],[0,-1],[0,1]]
    # 计算单元格被砸到的时间
    for i in range(M):
        # 陨石自己的时间,排除在自爆之前就已毁坏
        if time[g[i][0]][g[i][1]]==-1 or time[g[i][0]][g[i][1]]>g[i][2]:
            time[g[i][0]][g[i][1]] = g[i][2]
        # 遍历四个方向
        for j in range(4):
            x,y=g[i][0]+dic[j][0],g[i][1]+dic[j][1]
        # 位置合法
            if 0<=x<301 and 0<=y<301:
                # 空地 or 砸毁时间比现在时间短
                if time[x][y]==-1 or g[i][2]<time[x][y]:
                    time[x][y]=g[i][2]

    # 开始BFS搜索路径
    q=[]
    # [x,y,当前时刻time]
    q.append([0,0,0])
    # 不知道要不要这个
    visit[0][0]=True

    while len(q)!=0:
        p=q.pop(0)
        # 遍历四个方向
        if time[p[0]][p[1]]==-1:
            return time[p[0]][p[1]]
        for i in range(4):
            x, y = p[0] + dic[i][0], p[1] + dic[i][1]
            # 先检查坐标合法
            if 0 <= x < 301 and 0 <= y < 301:
                # 再判断是否为安全格子
                if time[x][y] == -1:
                    return p[2] + 1
            # 安全 or 炸毁时间-1比现在短，说明可以走
            if 0<=x<301 and 0<=y<=300 and visit[x][y]==False:
                if (time[x][y]==-1 or time[x][y]-1>p[2]):
                    q.append([x,y,p[2]+1])
                    visit[x][y]=True

    return -1


M=int(input())
# 陨石[x,y,time]
g=[list(map(int,input().split())) for i in range(M)]
# 格子砸毁时间表
time=[[-1]*301 for i in range(301)]
# 标记为未访问
visit=[[False]*301 for i in range(301)]
print(bfs())