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

typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

typedef struct {
    int val, left_val, right_val;
} InputNode;

Node* createNode(int val) {
    Node* n = (Node*)malloc(sizeof(Node));
    if (!n) {
        printf("Invalid input\n");
        exit(0);
    }
    n->val = val;
    n->left = NULL;
    n->right = NULL;
    return n;
}

void connectNodes(Node** nodes, int n, InputNode* inputs) {
    for (int i = 0; i < n; i++) {
        if (inputs[i].left_val != -1) {
            int found = 0;
            for (int j = 0; j < n; j++) {
                if (nodes[j]->val == inputs[i].left_val) {
                    nodes[i]->left = nodes[j];
                    found = 1;
                    break;
                }
            }
            if (!found) {
                printf("Invalid input\n");
                exit(0);
            }
        }
        if (inputs[i].right_val != -1) {
            int found = 0;
            for (int j = 0; j < n; j++) {
                if (nodes[j]->val == inputs[i].right_val) {
                    nodes[i]->right = nodes[j];
                    found = 1;
                    break;
                }
            }
            if (!found) {
                printf("Invalid input\n");
                exit(0);
            }
        }
    }
}

Node* findRoot(Node** nodes, int n, InputNode* inputs) {
    int* isChild = (int*)calloc(n, sizeof(int));
    if (!isChild) {
        printf("Invalid input\n");
        exit(0);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (inputs[j].left_val == inputs[i].val) isChild[i] = 1;
            if (inputs[j].right_val == inputs[i].val) isChild[i] = 1;
        }
    }
    int rootIndex = -1;
    for (int i = 0; i < n; i++) {
        if (!isChild[i]) {
            if (rootIndex != -1) {
                // More than one root
                free(isChild);
                return NULL;
            }
            rootIndex = i;
        }
    }
    free(isChild);
    if (rootIndex == -1) return NULL;
    return nodes[rootIndex];
}

int findPath(Node* root, int target, int* path, int idx) {
    if (!root) return 0;
    path[idx] = root->val;
    if (root->val == target) return idx + 1;
    if (target < root->val)
        return findPath(root->left, target, path, idx + 1);
    else
        return findPath(root->right, target, path, idx + 1);
}

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

    InputNode* inputs = (InputNode*)malloc(sizeof(InputNode) * N);
    if (!inputs) {
        printf("Invalid input\n");
        return 0;
    }

    for (int i = 0; i < N; i++) {
        if (scanf("%d %d %d", &inputs[i].val, &inputs[i].left_val, &inputs[i].right_val) != 3) {
            printf("Invalid input\n");
            free(inputs);
            return 0;
        }
        if (inputs[i].val < 1 || inputs[i].val > 100000 ||
            (inputs[i].left_val != -1 && (inputs[i].left_val < 1 || inputs[i].left_val > 100000)) ||
            (inputs[i].right_val != -1 && (inputs[i].right_val < 1 || inputs[i].right_val > 100000))) {
            printf("Invalid input\n");
            free(inputs);
            return 0;
        }
    }

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

    // Create nodes
    Node** nodes = (Node*)malloc(sizeof(Node) * N);
    if (!nodes) {
        printf("Invalid input\n");
        free(inputs);
        return 0;
    }

    for (int i = 0; i < N; i++) {
        nodes[i] = createNode(inputs[i].val);
    }

    connectNodes(nodes, N, inputs);

    Node* root = findRoot(nodes, N, inputs);
    if (!root) {
        printf("Invalid input\n");
        free(inputs);
        free(nodes);
        return 0;
    }

    int* path = (int*)malloc(sizeof(int) * N);
    if (!path) {
        printf("Invalid input\n");
        free(inputs);
        free(nodes);
        return 0;
    }

    int len = findPath(root, T, path, 0);
    if (len == 0) {
        printf("Invalid input\n"); // Target room not found
    } else {
        for (int i = 0; i < len; i++) {
            printf("%d", path[i]);
            if (i != len - 1) printf(" ");
        }
        printf("\n");
    }

    free(path);
    free(inputs);
    free(nodes);

    return 0;
}