#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
{
    Node* root;
public:

    FibonacciHeap()
    {
        root = NULL;
    }

    ~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);
    int extract_min_node();
    Node* extract_min_node(Node* n);
    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)
{
    cout<<"Insert ok\n";
    Node* x = new Node;
    x->key = newKey;
    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(FibonacciHeap &H)
{
    root = merge_nodes(root, H.root);
    cout<<"Revine in merge\n";
    H.root = NULL;
}

int  FibonacciHeap::extract_min()
{
    return root->key;
}

void FibonacciHeap::decrease_key(Node* x, int newKey)
{
    x->key = newKey;
    Node* y = x->parent;
    if ( y != NULL && 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 = NULL;
    newNode->child = NULL;
    newNode->degree = 0;
    newNode->mark = false;
    return newNode;
}


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

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)
{
    cout<<"In merge_nodes\n";
    if(a == NULL)
    {
        cout<<"In merge_nodes cu a vid\n";
        return b;
    }

    if(b == NULL)
    {
        cout<<"In merge_nodes cu b vid\n";
        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;
    cout<<"In merge_nodes, dupa executie\n";
    return a;
}

int FibonacciHeap::extract_min_node()
{
    Node* old = root;
    root = extract_min_node(root);
	int ret = old->key;
	delete old;
	return ret;
}

Node* FibonacciHeap::extract_min_node(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;
    consolidate();
}

void FibonacciHeap::unparent_all(Node* x)
{
    if(x == NULL)
        return;
    Node* y = x;
    do
    {
        y->parent = NULL;
        y = y->right;
    }
    while(y != x);
}


void FibonacciHeap::consolidate()
{
    int Dn = 64;
    Node** A = new Node*[Dn + 1];
    for(int i = 0; i < Dn + 1; i++)
    {
        A[i] = NULL;
    }
    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] != NULL)
        {
            auto tmp = A[d];
            if (e->key > tmp->key)
            {
                swap(e, tmp);
            }
            make_child(tmp, e);
            A[d++] = NULL;
        }
        A[e->degree] = e;
        root = e;
    }
    for (int i = 0; i < Dn + 1; i++)
    {
        if (A[i] != NULL && 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->left = child->right = child;
    child->parent = parent;
    parent->degree++;
    parent->child = merge_nodes(parent->child, child);
    child->mark = false;
}

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

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

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

vector <FibonacciHeap>v(200);

int main()
{

    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);
            cout<<"Dupa insert\n";
            //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;
}