#include <stdio.h>
#include <stdlib.h>

#define MAXN 10000
typedef struct Node {
    int val;
    struct Node *left, *right;
} Node;
Node* map[100001];
Node* newNode(int val) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->val = val;
    n->left = n->right = NULL;
    return n;
}
int findPath(Node* root, int target, int path[], int *pathLen) {
    if (!root) return 0;

    path[(*pathLen)++] = root->val;

    if (root->val == target) return 1;

    if (findPath(root->left, target, path, pathLen) ||
        findPath(root->right, target, path, pathLen))
        return 1;

    (*pathLen)--; 
    return 0;
}

int main() {
    int N;
    if (scanf("%d", &N) != 1 || N < 1 || N > MAXN) {
        printf("Invalid input\n");
        return 0;
    }

    int room, left, right;
    Node* root = NULL;
    int visited[100001] = {0};

    for (int i = 0; i < N; i++) {
        if (scanf("%d %d %d", &room, &left, &right) != 3 ||
            room < 1 || room > 100000 ||
            (left != -1 && (left < 1 || left > 100000)) ||
            (right != -1 && (right < 1 || right > 100000))) {
            printf("Invalid input\n");
            return 0;
        }

        if (!map[room]) map[room] = newNode(room);
        Node* curr = map[room];

        if (i == 0) root = curr;

        if (visited[room]) { 
            printf("Invalid input\n");
            return 0;
        }
        visited[room] = 1;

        if (left != -1) {
            if (!map[left]) map[left] = newNode(left);
            curr->left = map[left];
        }

        if (right != -1) {
            if (!map[right]) map[right] = newNode(right);
            curr->right = map[right];
        }
    }

    int target;
    if (scanf("%d", &target) != 1 || target < 1 || target > 100000) {
        printf("Invalid input\n");
        return 0;
    }

    int path[MAXN], pathLen = 0;
    if (!findPath(root, target, path, &pathLen)) {
        printf("Invalid input\n");
        return 0;
    }

    for (int i = 0; i < pathLen; i++) {
        if (i > 0) printf(" ");
        printf("%d", path[i]);
    }
    printf("\n");

    return 0;
}c