#include <bits/stdc++.h>

using namespace std;

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

struct nod{
    int value;
    nod * left = NULL, * next = NULL;
};

void add(nod * dest, nod * src)
{
    if(dest->left == NULL)
    {
        dest->left = src;
    }
    else
    {
        src->next = dest->left;
        dest->left = src;
    }
}

nod * merge(nod * a, nod * b)
{
    if(a == NULL) return b;
    if(b == NULL) return a;

    if(a->value > b->value) {
        add(a, b);
        return a;
    }
    else {
        add(b, a);
        return b;
    }

    return NULL;
}

nod * insert (nod * dest, int x)
{
    nod * nou = new nod;
    nou->value = x;
    return merge(dest, nou);
}

nod * dilit(nod * src)
{
    if(src == NULL || src->next == NULL)
    {
        return src;
    }
    else
    {
        nod * a = src;
        nod * b = src->next;
        nod * nou = b->next;

        a->next = NULL;
        b->next = NULL;

        return merge(merge(a,b), dilit(nou));
    }
}

class PairingHeap
{
public:
    nod * root;
    PairingHeap()
    {
        root = NULL;
    }
    void Insert(int x)
    {
        root = insert(root, x);
    }
    void Join(PairingHeap &src)
    {
        root = merge(root, src.root);
        src.root = NULL;
    }
    void Delete()
    {
        fout << root->value << '\n';
        root = dilit(root->left);
    }

};

int main() {
    int n,i,j,k,q,t,m,el;
    fin>>n>>q;
    vector<PairingHeap> v(n+1);
    for(i=1; i<=q;i++)
    {
        fin>>t>>m;
        if(t == 1)
        {
            fin>>el;
            v[m].Insert(el);
        }
        if(t == 2)
        {
            v[m].Delete();
        }
        if(t == 3)
        {
            fin>>el;
            v[m].Join(v[el]);
        }
    }
    return 0;
}