#include <vector>
#include <cmath>
#include <algorithm>
#include <fstream>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <iostream>
using namespace std;
ifstream f("mergeheap.in");
ofstream g("mergeheap.out");

class RpNode {
public:
    int value, rank;
    RpNode* parent;
    RpNode* left_child;
    RpNode* right_sibling;

    RpNode(int val) : value(val), rank(0), parent(nullptr), left_child(nullptr), right_sibling(nullptr) {}
};

class RankPairingHeap {
public:
    RpNode* root;

    RankPairingHeap() : root(nullptr) {}

    void insert(int value) {
        RpNode* new_node = new RpNode(value);
        root = link(root, new_node);
    } // op_id = 1
/*
    void delete_value(int value) {
        RpNode* node = find_node(root, value);
        if (!node) return;
        node->value = INT_MIN;
        bubble_up(node);
        extract_min();
    }
*/
    int contains(int value) const { return contains_in_subtree(root, value) ? 1 : 0; }

    int max_leq(int x) const { return max_leq_in_subtree(root, x, INT_MIN); }

    int min_geq(int x) const { return min_geq_in_subtree(root, x, INT_MAX); }

    vector<int> sorted_range(int x, int y) const {
        vector<int> result;
        collect_in_range(root, x, y, result);
        sort(result.begin(), result.end());
        return result;
    }

    void meld(RankPairingHeap& other) {
        root = link(root, other.root);
        other.root = nullptr;
    }

    void extract_min(int& res) {
        if (!root) return;

        vector<RpNode*> children;
        RpNode* child = root->left_child;
        while (child) {
            RpNode* next = child->right_sibling;
            child->parent = nullptr;
            child->right_sibling = nullptr;
            children.push_back(child);
            child = next;
        }
        res = root->value;
        delete root;
        root = nullptr;
        for (RpNode* c : children) {
            root = link(root, c);
        }
    }

private:
    static RpNode* link(RpNode* a, RpNode* b) {
        if (!a) return b;
        if (!b) return a;
        if (b->value < a->value)
            swap(a, b);

        b->right_sibling = a->left_child;
        if (b->right_sibling)
            b->right_sibling->parent = b;
        a->left_child = b;
        b->parent = a;

        return a;
    }

    static void bubble_up(RpNode* node) {
        while (node->parent && node->value < node->parent->value) {
            swap(node->value, node->parent->value);
            node = node->parent;
        }
    }

    static RpNode* find_node(RpNode* node, int value) {
        if (!node) return nullptr;
        if (node->value == value) return node;
        RpNode* found = find_node(node->left_child, value);
        if (found) return found;
        return find_node(node->right_sibling, value);
    }

    static bool contains_in_subtree(const RpNode* node, int value) {
        if (!node) return false;
        if (node->value == value) return true;
        if (contains_in_subtree(node->left_child, value)) return true;
        return contains_in_subtree(node->right_sibling, value);
    }

    static int max_leq_in_subtree(const RpNode* node, int x, int best) {
        if (!node) return best;
        if (node->value <= x && node->value > best)
            best = node->value;
        int left_best = max_leq_in_subtree(node->left_child, x, best);
        return max_leq_in_subtree(node->right_sibling, x, left_best);
    }

    static int min_geq_in_subtree(const RpNode* node, int x, int best) {
        if (!node) return best;
        if (node->value >= x && node->value < best)
            best = node->value;
        int left_best = min_geq_in_subtree(node->left_child, x, best);
        return min_geq_in_subtree(node->right_sibling, x, left_best);
    }

    static void collect_in_range(const RpNode* node, int x, int y, vector<int>& result) {
        if (!node) return;
        if (node->value >= x && node->value <= y)
            result.push_back(node->value);
        collect_in_range(node->left_child, x, y, result);
        collect_in_range(node->right_sibling, x, y, result);
    }
};

int main() {
    int n, q, op_id, heap_id, x;
    f >> n >> q;
    vector<RankPairingHeap> rpheaps(n+1);
    for (int i = 0; i < q; i++) {
        f >> op_id >> heap_id;
        switch (op_id) {
            case 1: {
                f >> x;
                rpheaps[heap_id].insert(-x);
                break;
            }
            case 2: {
                int res = 0;
                rpheaps[heap_id].extract_min(res);
                g << -res << '\n';
                break;
            }
            case 3: {
                f >> x;
                rpheaps[heap_id].meld(rpheaps[x]);
                break;
            }
        }
    }
    f.close();
    g.close();
    return 0;
}