#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;
    int dim;

    FibonacciHeap()
    {
        root = nullptr;
        dim = 0;
    }

    ~FibonacciHeap()
    {
        clear(root);
    }
    Node* insert(int newKey);
    void merge(FibonacciHeap &H);
    int  extract_min();
    void decrease_key(Node* x, int newKey);
    void delete_node(Node* x);

    static const int minimumKey;
    Node* create_node(int newKey);
    void insert_node(Node* newNode);
    void remove_from_list(Node* x);
    Node* merge_nodes(Node* a, Node* b);
    void make_child(Node *child, Node *parent);
    void consolidate();
    void unparent_all(Node* x);
    Node* extract_min_node();
    void cut(Node* x, Node* y);
    void cascading_cut(Node* y);
    void clear(Node* x);
};

const int FibonacciHeap::minimumKey = 0x80000000;

Node* FibonacciHeap::insert(int newKey)
{
    Node* newNode = create_node(newKey);
    insert_node(newNode);
    return newNode;
}

void FibonacciHeap::merge(FibonacciHeap &H)
{
    root = merge_nodes(root, H.root);
    dim += H.dim;
    H.root = nullptr;
    H.dim = 0;
}

int  FibonacciHeap::extract_min()
{
    Node* minNode = extract_min_node();
    int toReturn = minNode->key;
    delete minNode;
    return toReturn;
}

void FibonacciHeap::decrease_key(Node* x, int newKey)
{
    x->key = newKey;
    Node* y = x->parent;
    if ( y != nullptr && x->key < y->key )
    {
        cut(x, y);
        cascading_cut(y);
    }
    if (x->key < root->key)
        root = x;
}

void FibonacciHeap::delete_node(Node* x)
{
    decrease_key(x, minimumKey);
    extract_min();
}

Node* FibonacciHeap::create_node(int newKey)
{
    Node* newNode = new Node;
    newNode->key = newKey;
    newNode->left = newNode;
    newNode->right = newNode;
    newNode->parent = nullptr;
    newNode->child = nullptr;
    newNode->degree = 0;
    newNode->mark = false;
    return newNode;
}


void FibonacciHeap::insert_node(Node* newNode)
{
    root = merge_nodes( root, newNode);
    dim++;
}

void FibonacciHeap::remove_from_list(Node* x)
{
    if (x->right == x)
        return;
    Node* left_sib = x->left;
    Node* right_sib = x->right;
    left_sib->right = right_sib;
    right_sib->left = left_sib;
    x->left = x->right = x;
}


Node* FibonacciHeap::merge_nodes(Node* a, Node* b)
{
    if(a == nullptr)
        return b;
    if(b == nullptr)
        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;
}

Node* FibonacciHeap::extract_min_node()
{
    Node* mn = root;
    if (mn == nullptr)
    {
        return nullptr;
    }
    unparent_all(mn->child);
    merge_nodes(mn, mn->child);
    if (mn == mn->right)
    {
        root = nullptr;
    }
    else
    {
        root = mn->right;
    }
    remove_from_list(mn);
    if (root != nullptr)
    {
        consolidate();
    }
    dim--;
    return mn;
}

/*make all nodes' parent nullptr in a circular list*/
void FibonacciHeap::unparent_all(Node* x)
{
    if(x == nullptr)
        return;
    Node* y = x;
    do
    {
        y->parent = nullptr;
        y = y->right;
    }
    while(y != x);
}


void FibonacciHeap::consolidate()
{
    int Dn = (int)(log2(dim) / log2(1.618));
    Node** A = new Node*[Dn + 1];
    for(int i = 0; i < Dn + 1; i++)
    {
        A[i] = nullptr;
    }
    vector<Node*> nodeList;
    auto node = root;
    do
    {
        nodeList.emplace_back(node);
        node = node->right;
    }
    while (node != root);
    for (auto e: nodeList)
    {
        int d = e->degree;
        remove_from_list(e);
        while(A[d] != nullptr)
        {
            auto tmp = A[d];
            if (e->key > tmp->key)
            {
                swap(e, tmp);
            }
            make_child(tmp, e);
            A[d++] = nullptr;
        }
        A[e->degree] = e;
        root = e;
    }
    for (int i = 0; i < Dn + 1; i++)
    {
        if (A[i] != nullptr && A[i] != root)
        {
            merge_nodes(root, A[i]);
        }
    }
    Node* flag = root;
    Node* iter = flag;
    do
    {
        if (iter->key < root->key)
        {
            root = iter;
        }
        iter = iter->right;
    }
    while (iter != flag);
    delete []A;
}


void FibonacciHeap::make_child(Node *child, Node *parent)
{
    child->parent = parent;
    parent->child = merge_nodes(parent->child, child);
    parent->degree++;
    child->mark = false;
}

void FibonacciHeap::cut(Node* x, Node* y)
{
    y->child = (x == x->right ? nullptr : x->right);
    remove_from_list(x);
    y->degree--;
    merge_nodes(root, x);
    x->parent = nullptr;
    x->mark = false;
}

void FibonacciHeap::cascading_cut(Node* y)
{
    Node* z = y->parent;
    if ( z != nullptr)
    {
        if( y->mark == false)
            y->mark = true;
        else
        {
            cut(y,z);
            cascading_cut(z);
        }
    }
}


/*********************************************************************
* t1 is used to traversal the circular list.
  When t1 == x for the second time (the first time is at t1's initialization),
  t1 has completed the traversal.
**********************************************************************/
void FibonacciHeap::clear(Node* x)
{
    if ( x != nullptr )
    {
        Node* t1 = x;
        do
        {
            Node* t2 = t1;
            t1 = t1->right;
            clear(t2->child);
            delete t2;
        }
        while(t1 != x);
    }
}

int main()
{
    vector <FibonacciHeap>v(200);
    int nrHeaps, nrop;
    fin>>nrHeaps>>nrop;
    //*v[0].insert(4);

    for(int i = 0; i < nrop; i++)
    {
        int tip, x, a, b;
        fin>>tip;

        if(tip == 1)
        {
            fin>>a>>b;
            v[a].insert(-b);
            //v[a].afis(v[a].root);
        }
        else if(tip == 2)
        {
            fin>>x;
            fout<<-v[x].extract_min()<<'\n';
            v[x].extract_min_node();

        }
        else if(tip == 3)
        {
            fin>>a>>b;
            v[a].merge(v[b]);

        }
    }
    return 0;
}