```c #include

const int MAX_TIME = 1000; int M; typedef struct SequenceItem { int x; int y; } SequenceItem; typedef struct Sequence { int count; SequenceItem items[MAX_TIME + 1]; } Sequence;

const int INF = 50000; const int BREAK = 500001; const int LENGTH = 301;

int maxX = 0; int maxY = 0; int nextMaxX, nextMaxY; int maxTime = 0;

int tmpInt;

struct Sequence sequence[MAX_TIME + 1];

int main() { int position[LENGTH][LENGTH]; int x, y, time; int register i, j, xi, yi; int answer; answer = INF; maxX = 0, maxY = 0; for (i = 0; i < LENGTH - 1; i++) for (j = 0; j < LENGTH - 1; j++) position[i][j] = INF; position[0][0] = 0;

scanf(" %d", &M);
for (i = 0; i < M; ++i) {
    SequenceItem item;
    scanf(" %d %d %d", &item.x, &item.y, &time);
    sequence[time].items[sequence[time].count] = item;
    sequence[time].count += 1;
    if (maxTime < time) maxTime = time;
}

for (i = 0; i <= maxTime; ++i) {
    for (j = 0; j < sequence[i].count; j++) {
        x = sequence[i].items[j].x;
        y = sequence[i].items[j].y;
        position[x][y] = INF;
        if (x < LENGTH - 1) position[x + 1][y] = BREAK;
        if (y < LENGTH - 1) position[x][y + 1] = BREAK;
        if (0 < x) position[x - 1][y] = BREAK;
        if (0 < y) position[x][y - 1] = BREAK;
    }

    /* move */
    nextMaxX = maxX;
    nextMaxY = maxY;
    for (xi = 0; xi <= maxX; xi++) {
        for (yi = 0; yi <= maxY; yi++) {
            if (position[xi][yi] == i) {
                tmpInt = position[xi][yi] + 1;
                if (xi < LENGTH - 1) {
                    if (position[xi + 1][yi] == INF) {
                        position[xi + 1][yi] = tmpInt;
                        if (xi == maxX) nextMaxX = xi + 1;
                    }
                }
                if (xi != 0) {
                    if (position[xi - 1][yi] == INF) {
                        position[xi - 1][yi] = tmpInt;
                    }
                }
                if (yi < LENGTH - 1) {
                    if (position[xi][yi + 1] == INF) {
                        position[xi][yi + 1] = tmpInt;
                        if (yi == maxY) nextMaxY = yi + 1;
                    }
                }
                if (yi != 0) {
                    if (position[xi][yi - 1] == INF) {
                        position[xi][yi - 1] = tmpInt;
                    }
                }
            }
        }
    }
    maxX = nextMaxX;
    maxY = nextMaxY;
}
for (xi = 0; xi <= maxX; xi++) {
    for (yi = 0; yi <= maxY; yi++) {
        if (answer > position[xi][yi]) {
            answer = position[xi][yi];
        }
    }
}

if (answer == INF) answer = -1;

printf("%d\n", answer);
return 0; }