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

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

// Create new node
Node* newNode(int val) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->val = val;
    temp->left = temp->right = NULL;
    return temp;
}

// Find node by value in array
Node* findNode(Node** nodes, int N, int val) {
    for (int i = 0; i < N; i++)
        if (nodes[i]->val == val) return nodes[i];
    return NULL;
}

// Find inorder successor (min in right subtree)
Node* findMin(Node* root) {
    while (root && root->left) root = root->left;
    return root;
}

// Delete node using successor replacement
Node* deleteNodeSuccessor(Node* root, int val) {
    if (!root) return NULL;
    if (root->val == val) {
        // Node found
        if (!root->left) {
            Node* r = root->right;
            free(root);
            return r;
        } else if (!root->right) {
            Node* l = root->left;
            free(root);
            return l;
        } else {
            Node* succ = findMin(root->right);
            root->val = succ->val;
            root->right = deleteNodeSuccessor(root->right, succ->val);
        }
    } else {
        root->left = deleteNodeSuccessor(root->left, val);
        root->right = deleteNodeSuccessor(root->right, val);
    }
    return root;
}

// Inorder print with left/right values
void inorderPrint(Node* root) {
    if (!root) return;
    inorderPrint(root->left);
    int l = (root->left ? root->left->val : -1);
    int r = (root->right ? root->right->val : -1);
    printf("%d %d %d\n", root->val, l, r);
    inorderPrint(root->right);
}

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

    Node* nodes[10005];
    int leftVals[10005], rightVals[10005];

    for (int i = 0; i < N; i++) {
        int x, l, r;
        if (scanf("%d %d %d", &x, &l, &r) != 3) {
            printf("Invalid input\n");
            return 0;
        }
        nodes[i] = newNode(x);
        leftVals[i] = l;
        rightVals[i] = r;
    }

    // Connect children exactly as input
    for (int i = 0; i < N; i++) {
        if (leftVals[i] != -1) nodes[i]->left = findNode(nodes, N, leftVals[i]);
        if (rightVals[i] != -1) nodes[i]->right = findNod