#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <fstream>

using namespace std;

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

using namespace std;


struct Node
{
    int key;
    Node* left;
    Node* right;
    Node* parent;
    Node* child;
    int degree;
    bool mark;
};

class FibonacciHeap
{
public:
    Node* root;
    FibonacciHeap()
    {
        root = NULL;
    }
    ~FibonacciHeap()
    {
        if(root) clear(root);
    }
    Node* insert(int key);
    void merge_heaps(FibonacciHeap& H);
    Node* merge_nodes(Node* a, Node* b);
    int remove_min();
    void add_child(Node* parent, Node* child);
    void cascading_cut(Node* x);
    Node* remove_min(Node* x);
    void clear(Node* x);
};

Node* FibonacciHeap::insert(int key)
{
    Node* x = new Node;
    x->key = key;
    x->left = x->right = x;
    x->degree = 0;
    x->mark = false;
    x->child = NULL;
    x->parent = NULL;
    root = merge_nodes(root,x);
    return x;
}

void FibonacciHeap::merge_heaps(FibonacciHeap& H)
{
    root = merge_nodes(root,H.root);
    H.root = NULL;
}

Node* FibonacciHeap::merge_nodes(Node* a, Node* b)
{
    if(a == NULL)
        return b;
    if(b == NULL)
        return a;
    if(a->key > b->key)
    {
        Node* temp = a;
        a = b;
        b = temp;
    }
    Node* a_right = a->right;
    Node* b_left = b->left;
    a->right = b;
    b->left = a;
    a_right->left = b_left;
    b_left->right = a_right;
    return a;
}
int FibonacciHeap::remove_min()
{
    Node* old = root;
    root = remove_min(root);
    int ret = old->key;
    delete old;
    return ret;
}
void FibonacciHeap::add_child(Node* parent, Node* child)
{
    child->left = child->right = child;
    child->parent = parent;
    parent->degree++;
    parent->child = merge_nodes(parent->child,child);
}

void FibonacciHeap::cascading_cut(Node* x)
{
    if(x == NULL)
        return;
    Node* c = x;
    do
    {
        c->mark = false;
        c->parent = NULL;
        c = c->right;
    }
    while(c != x);
}

Node* FibonacciHeap::remove_min(Node* x)
{
    cascading_cut(x->child);
    if(x->right == x)
    {
        x = x->child;
    }
    else
    {
        x->right->left = x->left;
        x->left->right = x->right;
        x = merge_nodes(x->right,x->child);
    }
    if(x == NULL)
        return x;
    Node* A[64] = {NULL};
    while(true)
    {
        if(A[x->degree] != NULL)
        {
            Node* t = A[x->degree];
            if(t == x)
                break;
            A[x->degree] = NULL;
            if(x->key < t->key)
            {
                t->left->right = t->right;
                t->right->left = t->left;
                add_child(x,t);
            }
            else
            {
                t->left->right = t->right;
                t->right->left = t->left;
                if(x->right == x)
                {
                    t->right = t->left = t;
                    add_child(t,x);
                    x = t;
                }
                else
                {
                    x->left->right = t;
                    x->right->left = t;
                    t->right = x->right;
                    t->left = x->left;
                    add_child(t,x);
                    x = t;
                }
            }
            continue;
        }
        else
        {
            A[x->degree] = x;
        }
        x = x->right;
    }
    Node* Min = x;
    Node* temp = x;
    do
    {
        if(x->key < Min->key)
            Min = x;
        x = x->right;
    }
    while(x != temp);
    return Min;
}

void FibonacciHeap::clear(Node* x)
{
    if(x != NULL)
    {
        Node* temp = x;
        do
        {
            Node* d = temp;
            temp = temp->right;
            clear(d->child);
            delete d;
        }
        while(temp != x);
    }
}

int main()
{
    int nrHeaps, nrop;
    fin>>nrHeaps>>nrop;
    vector<FibonacciHeap> v(nrHeaps + 1);
    for(int i = 0; i < nrop; i++)
    {
        int tip, x, a, b;
        fin>>tip;

        if(tip == 1)
        {
            fin>>a>>b;
            v[a].insert(-b);
        }
        else if(tip == 2)
        {
            fin>>x;
            fout << -v[x].root->key << '\n';
            v[x].remove_min();
        }
        else if(tip == 3)
        {
            fin>>a>>b;
            v[a].merge_heaps(v[b]);
        }
    }
    return 0;
}