#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>
using namespace std;

struct TreapNode {
    int key, priority;
    TreapNode *left, *right;
};

// ----------------- Funcțiile definite inițial -----------------

TreapNode* rightRotate(TreapNode* y) {
    TreapNode *x = y->left;
    TreapNode *T2 = x->right;
    x->right = y;
    y->left = T2;
    return x;
}

TreapNode* leftRotate(TreapNode* x) {
    TreapNode *y = x->right;
    TreapNode *T2 = y->left;
    y->left = x;
    x->right = T2;
    return y;
}

TreapNode* newNode(int key) {
    TreapNode* temp = new TreapNode;
    temp->key = key;
    temp->priority = rand();
    temp->left = temp->right = nullptr;
    return temp;
}

TreapNode* insert(TreapNode* root, int key) {
    if (root == nullptr) return newNode(key);
    if (key <= root->key) {
        root->left = insert(root->left, key);
        if (root->left->priority > root->priority)
            root = rightRotate(root);
    } else {
        root->right = insert(root->right, key);
        if (root->right->priority > root->priority)
            root = leftRotate(root);
    }
    return root;
}

TreapNode* deleteNode(TreapNode* root, int key) {
    if (!root) return root;
    if (key < root->key) root->left = deleteNode(root->left, key);
    else if (key > root->key) root->right = deleteNode(root->right, key);
    else {
        if (!root->left) {
            TreapNode* temp = root->right;
            delete root;
            return temp;
        } else if (!root->right) {
            TreapNode* temp = root->left;
            delete root;
            return temp;
        } else if (root->left->priority < root->right->priority) {
            root = leftRotate(root);
            root->left = deleteNode(root->left, key);
        } else {
            root = rightRotate(root);
            root->right = deleteNode(root->right, key);
        }
    }
    return root;
}

TreapNode* mergeTreaps(TreapNode* left, TreapNode* right) {
    if (!left) return right;
    if (!right) return left;
    if (left->priority > right->priority) {
        left->right = mergeTreaps(left->right, right);
        return left;
    } else {
        right->left = mergeTreaps(left, right->left);
        return right;
    }
}

void split(TreapNode* root, int key, TreapNode*& left, TreapNode*& right) {
    if (!root) left = right = nullptr;
    else if (root->key <= key) {
        split(root->right, key, root->right, right);
        left = root;
    } else {
        split(root->left, key, left, root->left);
        right = root;
    }
}

bool contains(TreapNode* root, int key) {
    if (root == nullptr) return false;
    if (root->key == key) return true;
    if (key < root->key) return contains(root->left, key);
    return contains(root->right, key);
}

TreapNode* findMaxLessThanEqual(TreapNode* root, int X) {
    TreapNode* result = nullptr;
    while (root) {
        if (root->key <= X) {
            result = root;
            root = root->right;
        } else {
            root = root->left;
        }
    }
    return result;
}

TreapNode* findMinGreaterThanEqual(TreapNode* root, int X) {
    TreapNode* result = nullptr;
    while (root) {
        if (root->key >= X) {
            result = root;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return result;
}

void findRange(TreapNode* root, int X, int Y, vector<int>& result) {
    if (!root) return;
    if (root->key > Y) {
        findRange(root->left, X, Y, result);
    } else if (root->key < X) {
        findRange(root->right, X, Y, result);
    } else {
        findRange(root->left, X, Y, result);
        result.push_back(root->key);
        findRange(root->right, X, Y, result);
    }
}

// ------------------ Funcții utile pentru mergeheap ------------------

TreapNode* insertNode(TreapNode* root, TreapNode* node) {
    return mergeTreaps(root, node);
}

TreapNode* eraseMin(TreapNode* root, int& minVal) {
    if (!root->left) {
        minVal = root->key;
        TreapNode* newRoot = mergeTreaps(root->left, root->right);
        delete root;
        return newRoot;
    }
    root->left = eraseMin(root->left, minVal);
    return root;
}

void destroyTreap(TreapNode* root) {
    if (!root) return;
    destroyTreap(root->left);
    destroyTreap(root->right);
    delete root;
}

// ------------------ Soluție problema mergeheap ------------------

int main() {
    ifstream fin("mergeheap.in");
    ofstream fout("mergeheap.out");

    int N, Q;
    fin >> N >> Q;
    vector<TreapNode*> heaps(N + 1, nullptr);

    while (Q--) {
        int op;
        fin >> op;

        if (op == 1) {
            int m, x;
            fin >> m >> x;
            heaps[m] = insertNode(heaps[m], newNode(x));
        } else if (op == 2) {
            int m;
            int minVal;
            heaps[m] = eraseMin(heaps[m], minVal);
            fout << minVal << '\n';
        } else if (op == 3) {
            int a, b;
            fin >> a >> b;
            if (a == b) continue;
            heaps[a] = mergeTreaps(heaps[a], heaps[b]);
            heaps[b] = nullptr;
        }
    }

    for (int i = 1; i <= N; ++i)
        destroyTreap(heaps[i]);

    fin.close();
    fout.close();
    return 0;
}