#include <bits/stdc++.h>

using namespace std;

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

struct node
{
    int n;
    int degree;
    node *parent;
    node *child;
    node *left;
    node *right;
    char mark;

    char C;
};

// Implementation of Fibonacci heap
class FibonacciHeap
{
private:
    int nH;

    node *H;

public:
    node *InitializeHeap();
    int Fibonnaci_link(node *, node *, node *);
    node *Create_node(int);
    node *Insert(node *, node *);
    node *Union(node *, node *);
    node *Extract_Min(node *);
    int Consolidate(node *);
    int Display(node *);
    node *Find(node *, int);
    int Decrease_key(node *, int, int);
    int Delete_key(node *, int);
    int Cut(node *, node *, node *);
    int Cascase_cut(node *, node *);
    FibonacciHeap()
    {
        H = InitializeHeap();
    }
};

node *FibonacciHeap::InitializeHeap()
{
    node *np;
    np = NULL;
    return np;
}

node *FibonacciHeap::Create_node(int value)
{
    node *x = new node;
    x->n = value;
    return x;
}

node *FibonacciHeap::Insert(node *H, node *x)
{
    x->degree = 0;
    x->parent = NULL;
    x->child = NULL;
    x->left = x;
    x->right = x;
    x->mark = 'F';
    x->C = 'N';
    if (H != NULL)
    {
        (H->left)->right = x;
        x->right = H;
        x->left = H->left;
        H->left = x;
        if (x->n < H->n)
            H = x;
    }
    else
    {
        H = x;
    }
    nH = nH + 1;
    return H;
}

int FibonacciHeap::Fibonnaci_link(node *H1, node *y, node *z)
{
    (y->left)->right = y->right;
    (y->right)->left = y->left;
    if (z->right == z)
        H1 = z;
    y->left = y;
    y->right = y;
    y->parent = z;

    if (z->child == NULL)
        z->child = y;

    y->right = z->child;
    y->left = (z->child)->left;
    ((z->child)->left)->right = y;
    (z->child)->left = y;

    if (y->n < (z->child)->n)
        z->child = y;
    z->degree++;
}

node *FibonacciHeap::Union(node *H1, node *H2)
{
    node *np;
    node *H = InitializeHeap();
    H = H1;
    (H->left)->right = H2;
    (H2->left)->right = H;
    np = H->left;
    H->left = H2->left;
    H2->left = np;
    return H;
}

node *FibonacciHeap::Extract_Min(node *H1)
{
    node *p;
    node *ptr;
    node *z = H1;
    p = z;
    ptr = z;
    if (z == NULL)
        return z;

    node *x;
    node *np;

    x = NULL;

    if (z->child != NULL)
        x = z->child;

    if (x != NULL)
    {
        ptr = x;
        do
        {
            np = x->right;
            (H1->left)->right = x;
            x->right = H1;
            x->left = H1->left;
            H1->left = x;
            if (x->n < H1->n)
                H1 = x;

            x->parent = NULL;
            x = np;
        }
        while (np != ptr);
    }

    (z->left)->right = z->right;
    (z->right)->left = z->left;
    H1 = z->right;

    if (z == z->right && z->child == NULL)
        H = NULL;

    else
    {
        H1 = z->right;
        Consolidate(H1);
    }
    nH = nH - 1;
    return p;
}

int FibonacciHeap::Consolidate(node *H1)
{
    int d, i;
    float f = (log(nH)) / (log(2));
    int D = f;
    node *A[D];

    for (i = 0; i <= D; i++)
        A[i] = NULL;

    node *x = H1;
    node *y;
    node *np;
    node *pt = x;

    do
    {
        pt = pt->right;

        d = x->degree;

        while (A[d] != NULL)

        {
            y = A[d];

            if (x->n > y->n)

            {
                np = x;

                x = y;

                y = np;
            }

            if (y == H1)
                H1 = x;
            Fibonnaci_link(H1, y, x);
            if (x->right == x)
                H1 = x;
            A[d] = NULL;
            d = d + 1;
        }

        A[d] = x;
        x = x->right;

    }

    while (x != H1);
    H = NULL;
    for (int j = 0; j <= D; j++)
    {
        if (A[j] != NULL)
        {
            A[j]->left = A[j];
            A[j]->right = A[j];
            if (H != NULL)
            {
                (H->left)->right = A[j];
                A[j]->right = H;
                A[j]->left = H->left;
                H->left = A[j];
                if (A[j]->n < H->n)
                    H = A[j];
            }
            else
            {
                H = A[j];
            }
            if (H == NULL)
                H = A[j];
            else if (A[j]->n < H->n)
                H = A[j];
        }
    }
}
node* H[105];

int main()
{
    int n, q;
    fin >> n >> q;
    FibonacciHeap fs;

    for(int i = 1; i <= n; ++i)
        H[i] = fs.InitializeHeap();

    for(int i = 1; i <= q; ++i)
    {
        int tip;
        fin >> tip;
        if(tip == 1)
        {
            int wh, val;
            fin >> wh >> val;
            node* p = fs.Create_node(-val);
            H[wh] = fs.Insert(H[wh], p);
        }
        else if(tip == 3)
        {
            int wh1, wh2;
            fin >> wh1 >> wh2;
            H[wh1] = fs.Union(H[wh1], H[wh2]);
            H[wh2] = fs.InitializeHeap();
        }
        else
        {
            int wh;
            fin >> wh;
            node*p = fs.Extract_Min(H[wh]);
            fout << -p->n << '\n';
        }
        fout.flush();
    }
    return 0;
}