#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;
ifstream fin("mergeheap.in");
ofstream fout("mergeheap.out");

struct node{
    int key;
    int degree;
    node* parent,* child;
    node* left,* right;
};

class FibonacciHeap{
public:
    node* mini;
    int noNodes;

    FibonacciHeap();    // constructor -> declarat in afara clasei
    ~FibonacciHeap() {  // destructor
        _clear(mini);   // se distruge pointerul la minim
    }
    void insertNode(int newKey);
    void merge(FibonacciHeap& heap2);
    int  extractMin();
    void Display();

private:
    node* _createNode(int newKey);
    void _insertNode(node* nod);
    node* _merge(node* a, node* b);
    void _removeFromCircularList(node* nod);   // removing a node from the circular list he's in
    void _makeChild(node *child, node *parent);
    void _consolidate();
    void _unparentAll(node* nod);
    node* _extractMin_node();
    void _clear(node* nod);

};

// Constructorul
FibonacciHeap::FibonacciHeap() {
    mini = nullptr;
    noNodes = 0;
}

// INSERARE
void FibonacciHeap::insertNode(int newKey)
{
    node* nod = _createNode(newKey);
    _insertNode(nod);
}

// UNION
void FibonacciHeap::merge(FibonacciHeap &heap2) {   // pe heap2 il adauga ca fiu lui heap1
    mini = _merge(mini, heap2.mini);    // minimul din heap1 se merge-uieste cu minimul din heap2
    noNodes += heap2.noNodes;   // s-au adaugat nodurile din heap2 in heap1
    heap2.mini = nullptr;   // reinitializez heap2
    heap2.noNodes = 0;

}

// EXTRACT MIN
int FibonacciHeap::extractMin() {   // apelam extractia minului, luam valoarea din minim si o returnam pt afisare, stergem nodul
    node* minNode = _extractMin_node();
    int ret = minNode->key; // luam valoarea din minim pt afisare
    delete minNode;         // nodul poate fi sters acum
    return ret;
}

// CREATE NODE
node *FibonacciHeap::_createNode(int newKey) // cream nodul si stim si ce valoare va avea
{
    node *nod = new node;
    nod->key = newKey;
    nod->child = nod->parent = nullptr;
    nod->degree = 0;
    nod->left = nod->right = nod;   // initial, nodul abia creat va pointa stanga-dreapta doar spre el

    return nod;
}

// INSERT NODE  =  MERGE THE MIN IN THE LIST WITH THE NODE
void FibonacciHeap::_insertNode(node *nod) {
    mini = _merge(mini, nod);
    noNodes++;
}


//removing nod from the circular list he s in
void FibonacciHeap::_removeFromCircularList(node *nod) {
    if(nod->right == nod){
        // the list only has one node
        return;
    }

    node* leftNode;
    node* rightNode;

    leftNode = nod->left;
    rightNode = nod->right;

    leftNode->right = rightNode;
    rightNode->left = leftNode;
}

// UNION  of 2 nodes  =  se inlantuiesc in lista de minime => vom avea:  ceva1 <--> a <--> b <--> ceva2
node *FibonacciHeap::_merge(node *a, node *b)
{
    // daca unul din ele e nul, ramane doar celalalt la uniune
    if(a == nullptr)
        return b;
    if(b == nullptr)
        return a;

    if(b->key < a->key){    // daca a nu e deja minimul dintre cele 2 noduri, facem swap ca sa stim ca a e minimul
        node* aux = a;
        a = b;
        b = aux;
    }

    // cream 2 noduri temporare ca sa retinem pointerii pe care ii vom schimba
    node* aRight = a->right;
    node* bLeft = b->left;

    // acum: a pointeaza dreapta spre b si b pointeaza stanga spre a <=> a e in stanga lui b:   a <--> b
    a->right = b;
    b->left = a;

    aRight->left = bLeft;   // ce era la dreapta lui a (adica nodul care pointa stanga spre a) va pointa stanga spre ce pointa stanga din b
    bLeft->right = aRight;  // ce era in stanga lui b se va lega dreapta de ceea ce era in dreapta lui a
    // daca inainte aveam:   ceva1 <-->  a  <--> aright <--> ceva2           ceva3 <--> bleft <-->   b    <--> ceva4
    // acum avem:            ceva1 <-->  a  <-->   b    <--> ceva4           ceva3 <--> bleft <--> aright <--> ceva2

    return a;
}


// EXTRACT MIN
node *FibonacciHeap::_extractMin_node()
{
    node* min = mini;

    if(min != nullptr)  // daca heapul nu e gol (pt ca min e in varf la un heap => daca exista min, at. heapul nu e gol)
    {
        _unparentAll(min->child);      // unlink the children of the mini node
        _merge(min, min->child);       // merge the children (child circular list) to the root list
        _removeFromCircularList(min);  // remove

        if(min == min->right)   // daca in lista inlantuita era doar minimul pe care il extragem acum
            mini = nullptr;     // atunci o sa ramana vida <=> n-o sa mai existe niciun minim
        else                    // altfel
        {
            mini = min->right;  // actualizam minimumul
            _consolidate();     // consolidam heapurile din lista inlantuita ca sa nu avem mai multe de acelasi grad
        }
        noNodes--;
    }

    return min;   // returnez minimul pentru afisare
}


void FibonacciHeap::_unparentAll(node *nod) // stergem legatura cu parintele
{
    if(nod == nullptr)  //the node doesn't exist
        return;

    node* aux = nod;

    aux->parent = nullptr;
    aux = aux->right;   // mergem si pe frati si facem acelasi lucru:

    while(aux != nod)
    {
        aux->parent = nullptr;
        aux = aux->right;
    }
}


void FibonacciHeap::_consolidate()
{
    int degree = (log(noNodes)) / log(2);

    node* d[degree + 1]; // array de pointeri de heapuri pentru toate gradele (de la 0 la gradul maxim existent)

    for(int i = 0; i <= degree; i++) // initial la fiecare grad nu am niciun pointer(heap) inca
        d[i] = nullptr;

    d[mini->degree] = mini; // acum stiu gradul minimului deci ca valoare ii pun minimul

    // we check all the nodes in the root list for their degree
    // when two nodes have the same degree, we link them (parent-child ) relationship

    bool done = false;
    node* aux = mini;

    while(true)
    {
        int deg = aux->degree;
        while(d[deg] != nullptr){
            node* otherNode = d[deg];

            if(aux == otherNode)    // daca m-am intors in nodul(heapul) in care am fost deja
            {
                done = true;        // inseamna ca am terminat si pot iesi
                break;
            }
            _makeChild(otherNode, aux); // altfel, le unesc intr-un singur heap
            d[deg] = nullptr;           // sterg gradul nodului pe care l-am atasat la celalalt heap
            deg++;                      // iar gradul celui ramas creste cu 1 pentru ca i-am adaugat un fiu
        }

        if(done) break; // daca am iesit din while-ul interior pentru ca am terminat procesul, atunci ies si din cel exterior si apoi din functie

        d[aux->degree] = aux;   // actualizez gradul
        aux = aux->right;   // merg in continuare pe frati
    }

    mini = aux; // actualizez minimul => trebuie sa parcurg toata lista de radacini ca sa vad cu ce minim am ramas:
    for(node* i = aux->right; i != aux; i = i->right)
        if(i->key < mini->key)
            mini = i;

}


// MERGE-UIREA NOULUI COPIL AL UNUI NOD CU CEILALTI COPII PE CARE II AVEA NODUL
void FibonacciHeap::_makeChild(node *child, node *parent) // linking tree 1 to tree 2
{
    node* aux;
    if(child->key > parent->key) // vreau sa am in copil minimul
    {
        aux = child;
        child = parent;
        parent = aux;
    }

    _removeFromCircularList(child); // nu mai am ca radacina pe copil

    child->left = child->right = child; // pointeaza si stanga si dreapta tot spre el

    child->parent = parent; // pointeaza spre parinte

    parent->child = _merge(parent->child, child);   // noul copil se uneste cu copiii noului parinte <=> se adauga copilul in lista de copii a parintelui

    parent->degree++;   // creste gradul parintelui pt ca i-am mai adaugat un copil
}


void FibonacciHeap::_clear(node *nod) // stergem nodul = eliberam memoria
{
    if(nod)
    {
        node* aux = nod;
        // stergem copiii recursiv
        do {
            node* aux1 = aux;
            aux = aux->right;
            _clear(aux1->child);
            delete aux1;
        } while(aux != nod);
    }
}


void FibonacciHeap::Display() {
    node* aux = mini;

    if(aux == nullptr){
        cout << "\nThe heap is empty\n";
        return;
    }
    cout << "The root nodes of the heap are: \n";
    do{
        cout << aux->key << " " ;
        aux = aux->right;
        if(aux != mini){
            cout << "-->";
        }

    } while (aux != mini && aux != nullptr);

    cout <<"\n\n";
}


int main() {
    FibonacciHeap h[101];

    int n,q,m,op,a,b,x;
    fin>>n>>q;
    for (int i=0; i<q; i++){
        fin>>op;
        if (op==1){
            fin>>m>>x;
            h[m].insertNode((-1)*x);
        }
        else if (op==2){
            fin>>m;
            fout<<(-1)*h[m].extractMin()<<endl;
        }
        else {
            fin>>a>>b;
            h[a].merge(h[b]);
        }
    }

    return 0;
}