#include <bits/stdc++.h>
using namespace std;
ifstream f ("mergeheap.in");
ofstream g ("mergeheap.out");

///creez o clasa numita nodes, care sa contina toate 'atributele' specifice unui nod din arbore
class Nodes {
private:
    Nodes *pointertotheParent;
    Nodes *pointertotheChild;
    Nodes *pointertotheLeft;
    Nodes *pointertotheRight;

    int valueoftheNode;
    int degreeoftheNode;
    bool mark;///this variable will be used for the decreaseKey operation

public:
    int getValueoftheNode() { return this->valueoftheNode;}
    int getdegreeoftheNode() {return this->degreeoftheNode;}
    bool getmark() {return this->mark;}
    Nodes* getpointertotheParent() { return this->pointertotheParent;}
    Nodes* getpointertotheChild() { return this->pointertotheChild;}
    Nodes* getpointertotheLeft() { return this-> pointertotheLeft;}
    Nodes* getpointertotheRight() { return this -> pointertotheRight;}

    void setValueoftheNode(int value) { this->valueoftheNode=value;}
    void setdegreeoftheNode(int value) {this->degreeoftheNode=value;}
    void setmark(bool value) {this->mark=value;}
    void setpointertotheParent(Nodes* value) {this->pointertotheParent=value;}
    void setpointertotheChild(Nodes* value) {this->pointertotheChild=value;}
    void setpointertotheLeft(Nodes* value) {this->pointertotheLeft=value;}
    void setpointertotheRight(Nodes* value) {this->pointertotheRight=value;}
};

class FibonacciHeap {
public:
    int NumberofNodes;
    Nodes *PointertotheMinimum = NULL;

    Nodes* getPointertotheMinimum() {return this->PointertotheMinimum;}
    void setPointertotheMinimum(Nodes* PointerMin){ this->PointertotheMinimum = PointerMin; }

///Operatia de inserare
    void InserttotheHeap(int value) {
        Nodes *node = new Nodes();
        node->setValueoftheNode(value);
        node->setpointertotheParent(NULL);
        node->setpointertotheChild(NULL);
        node->setpointertotheLeft(node);
        node->setpointertotheRight(node);

        if (PointertotheMinimum != NULL) {
            (PointertotheMinimum->getpointertotheLeft())->setpointertotheRight(node);
            node->setpointertotheRight(PointertotheMinimum);
            node->setpointertotheLeft(PointertotheMinimum->getpointertotheLeft());
            PointertotheMinimum->setpointertotheLeft(node);
            if (node->getValueoftheNode() > PointertotheMinimum->getValueoftheNode()) {
                PointertotheMinimum = node;
            }
        } else
            PointertotheMinimum = node;

        NumberofNodes += 1;
    }

    void WritetheHeap(Nodes *PointertotheMinimum) {
        Nodes *aux = PointertotheMinimum;
        if (aux == NULL) {
            cout << "The heap does not contain any nodes" << endl;
            return;
        } else {
            cout << "Root nodes: " << endl;
            do {
                cout << aux->getValueoftheNode();
                aux = aux->getpointertotheRight();
                if (PointertotheMinimum != aux)
                    cout << "-->";
            } while (aux != PointertotheMinimum && aux->getpointertotheRight() != NULL);
            cout << endl;
        }
    }

    Nodes *UnionoftwoHeaps(Nodes *H1, Nodes *H2) {
        Nodes *PrincipalH;
        Nodes *aux;

        PrincipalH = H1;
        (PrincipalH->getpointertotheLeft())->setpointertotheRight(H2);
        (H2->getpointertotheLeft())->setpointertotheRight(PrincipalH);
        aux = PrincipalH->getpointertotheLeft();
        (PrincipalH->setpointertotheLeft(H2->getpointertotheLeft()));
        H2->setpointertotheLeft(aux);

        return PrincipalH;
    }

    void Link_FibonacciRoots(Nodes *PointerMinimum, Nodes *ExistingRoot, Nodes *MinRoot) {
        (ExistingRoot->getpointertotheLeft())->setpointertotheRight(ExistingRoot->getpointertotheRight());
        (ExistingRoot->getpointertotheRight())->setpointertotheLeft(ExistingRoot->getpointertotheLeft());

        ///cele doua linii de cod, sterg de fapt nodul Existing Root(redirectioneaza vecinii)
        ExistingRoot->setpointertotheLeft(ExistingRoot);
        ExistingRoot->setpointertotheRight(ExistingRoot);
        ExistingRoot->setpointertotheParent(MinRoot);

        if (MinRoot->getpointertotheChild() == NULL)
            MinRoot->setpointertotheChild(ExistingRoot);

        ///mai sus, am mutat ExistingRoot pe urmatorul nivel
        ExistingRoot->setpointertotheRight(MinRoot->getpointertotheChild());
        ExistingRoot->setpointertotheLeft((MinRoot->getpointertotheChild())->getpointertotheLeft());
        ((MinRoot->getpointertotheChild())->getpointertotheLeft())->setpointertotheRight(ExistingRoot);
        (MinRoot->getpointertotheChild())->setpointertotheLeft(ExistingRoot);

        if (ExistingRoot->getValueoftheNode() > (MinRoot->getpointertotheChild())->getValueoftheNode())
            MinRoot->setpointertotheChild(ExistingRoot);
        ///in if ul de mai sus, verificam daca nodul care deja era copilul radacinii in care ne aflam este mai mare decat
        ///nodul pe care tocmai l am cocborat, iar in cazul afirmativ, pointerul de copil va pointa catre valoarea mai mica

        MinRoot->setdegreeoftheNode(MinRoot->getdegreeoftheNode() + 1);
    }

    void *ConsolidateHeap(Nodes *PointerMinimum) {
        int degree = int(log2(NumberofNodes)), node_degree;
        Nodes *Vector[degree + 1]; ///in vector vom stoca arborii de grad corespunzator

        int i;
        for (i = 0; i <= degree; i++)
            Vector[i] = NULL;
        ///initializez fiecare pozitie din vctor cu valoarea NULL

        Nodes *MinRoot = PointerMinimum;
        do {
            node_degree = MinRoot->getdegreeoftheNode();
            while (Vector[node_degree] != NULL) {
                Nodes *ExistingRoot = Vector[node_degree];
                if (MinRoot->getValueoftheNode() > ExistingRoot->getValueoftheNode()) {
                    swap(MinRoot, ExistingRoot);
                }
                Link_FibonacciRoots(PointerMinimum, ExistingRoot, MinRoot);
                if (MinRoot->getpointertotheRight() == MinRoot) {
                    PointerMinimum = MinRoot;
                }
                Vector[node_degree] = NULL; ///punem NULL pt ca in interiorul functiei de link, se sterge de pe lista de radacini nodul care va deveni copil
                node_degree = node_degree + 1;
            }
            Vector[node_degree] = MinRoot;
            MinRoot = MinRoot->getpointertotheRight();

        } while (MinRoot != PointerMinimum);
        ///do while ul va functiona cat timp nu va ajunge iarasi la primul nod din lista(pointerul catre min)

        ///Rebuild Heap
        int j;
        Nodes *NewpointerMin = NULL;

        for (j = 0; j <= degree; j++) {
            if (Vector[j] != NULL) {
                Vector[j]->setpointertotheLeft(Vector[j]);
                Vector[j]->setpointertotheRight(Vector[j]);

                if (NewpointerMin != NULL) {
                    (NewpointerMin->getpointertotheLeft())->setpointertotheRight(Vector[j]);
                    Vector[j]->setpointertotheRight(NewpointerMin);
                    Vector[j]->setpointertotheLeft(NewpointerMin->getpointertotheLeft());
                    NewpointerMin->setpointertotheLeft(Vector[j]);

                    if (Vector[j]->getValueoftheNode() > NewpointerMin->getValueoftheNode())
                        NewpointerMin = Vector[j];
                } else
                    NewpointerMin = Vector[j];
            }
        }
    }

    Nodes *TakeMin(Nodes *PointertothePointertotheMin) {
        if (PointertotheMinimum == NULL)
            return PointertotheMinimum;

        Nodes *Min = PointertotheMinimum;
        Nodes *ReturnedValue;
        ReturnedValue = Min;
        Nodes *Child = NULL;
        Nodes *FirstChild;
        Nodes *NextChild;

        if (Min->getpointertotheChild() != NULL)
            Child = Min->getpointertotheChild();

        if (Child != NULL) {
            FirstChild = Child;   ///retinem primul copil ca sa stim atunci cand ajunge iarasi la inceputul listei inlantuite
            do {
                NextChild = Child->getpointertotheRight();
                (PointertotheMinimum->getpointertotheLeft())->setpointertotheRight(Child);
                Child->setpointertotheRight(PointertotheMinimum);
                Child->setpointertotheLeft(PointertotheMinimum->getpointertotheLeft());
                PointertotheMinimum->setpointertotheLeft(Child);

                Child->setpointertotheParent(NULL);
                Child = NextChild;

            } while (NextChild != FirstChild);
        }

        ///in urmatoarele trei linii de cod, modificam pointerii astfel incat Pointerul de min sa arate spre urmatorul nod inserat, adica primul copil
        (Min->getpointertotheLeft())->setpointertotheRight(Min->getpointertotheRight());
        (Min->getpointertotheRight())->setpointertotheLeft(Min->getpointertotheLeft());
        PointertotheMinimum = Min->getpointertotheRight();

        ///in urmatoarea linie, verificam daca nu cumva nodul de minim este singurul nod care a ramas in heap
        if (PointertotheMinimum->getpointertotheChild() == NULL &&
            PointertotheMinimum == PointertotheMinimum->getpointertotheRight())
            cout << "Heapul este NULL";

        else {
            PointertotheMinimum = Min->getpointertotheRight();
            ConsolidateHeap(PointertotheMinimum);
        }

        NumberofNodes = NumberofNodes - 1;
        return ReturnedValue;
    }
};
int main()
{

    /*FibonacciHeap.InserttotheHeap(4);
    FibonacciHeap.InserttotheHeap(3);
    InserttotheHeap(7);
    InserttotheHeap(5);
    InserttotheHeap(2);
    InserttotheHeap(1);
    InserttotheHeap(10);
    InserttotheHeap(0);
    InserttotheHeap(2);
    InserttotheHeap(20);

    ConsolidateHeap(PointertotheMinimum);
    cout<<TakeMin(PointertotheMinimum)->getValueoftheNode()<<endl;

    WritetheHeap(PointertotheMinimum);
    return 0;

    */
    int n, q,i, first,second, third;
    vector <FibonacciHeap*> heap;
    f>>n>>q;
    for( i=0; i<n; i++){
        heap.push_back(new FibonacciHeap ());
    }

    while(q>0){
        f>>first;
        if(first == 2) f>>second;
        else f>>second>>third;
        switch(first){
            case 1: {
                heap[second]->InserttotheHeap(third);
                break;
            }
            case 2: {
                g<<(heap[second]->TakeMin(heap[second]->getPointertotheMinimum()))->getValueoftheNode()<<endl;
                break;
            }
            case 3: {
                if(heap[third]->getPointertotheMinimum()->getValueoftheNode() > heap[second]->getPointertotheMinimum()->getValueoftheNode()){
                    heap[second]->setPointertotheMinimum(heap[second]->UnionoftwoHeaps(heap[third]->getPointertotheMinimum(), heap[second]->getPointertotheMinimum()));
                    heap[third]->setPointertotheMinimum(NULL);
                } else{
                    heap[second]->setPointertotheMinimum(heap[second]->UnionoftwoHeaps(heap[second]->getPointertotheMinimum(), heap[third]->getPointertotheMinimum()));
                    heap[third]->setPointertotheMinimum(NULL);
                }

                break;
            }
            default: {
                break;
            }
        }
        q--;
    }
    f.close();
    g.close();
    return 0;
}