#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

const int MAXN = (int)1e6 + 7;
const int INF = (int)1e9 + 7;
const ll LINF = (ll)4e18 + 7LL;
const double eps = 1e-8;

#define TASK "rmq"

struct Heap;

const int C = 25;

struct Tree {

    vector<Tree*> g;
    ll val;
    int index;
    int rank;
    Heap* h;
    Tree* pr;

    Tree(ll x, int Ind) {
        pr = 0;
        val = x;
        index = Ind;
        rank = 0;
        h = 0;
    }
};

Tree* merge(Tree* a, Tree* b) {
    if (!a)
        return b;
    if (!b)
        return a;
    if (a->val < b->val || (a->val == b->val && a->index < b->index)) {
        b->pr = a;
        a->g.push_back(b);
        ++(a->rank);
        return a;
    } else {
        a->pr = b;
        b->g.push_back(a);
        ++(b->rank);
        return b;
    }
}

struct Heap {

    Tree* a[C];
    int Ind;

    Heap() {
        for (int i = 0; i < C; ++i)
            a[i] = 0;
    }

    Heap(Tree *t) {
        for (int i = 0; i < C; ++i)
            a[i] = 0;
        a[t->rank] = t;
    }

    ll getMin() {
        ll mn = LINF;
        for (int i = 0; i < C; ++i)
            if (a[i])
                mn = min(mn, a[i]->val);
        return mn;
    }
};

void print(Tree *t) {
    if (!t) {
        cout << "empty1 ";
        return;
    }
    cout << t->val << " ";
    for (auto to : t->g) {
        print(to);
    }
}

void print(Heap *h) {
    if (!h) {
        cout << "empty" << endl;
        return;
    }
    for (int i = 0; i < C; ++i) {
        print(h->a[i]);
        cout << endl;
    }
}

Heap* merge(Heap* a, Heap* b) {
    Tree* last = 0;
    for (int i = 0; i < C; ++i) {
        Tree* t = merge(a->a[i], b->a[i]);
        if (!t) {
            a->a[i] = last;
            last = 0;
        } else if (t->rank == i) {
            a->a[i] = t;
            if (last) {
                last = merge(a->a[i], last);
                a->a[i] = 0;
            }
        } else {
            a->a[i] = last;
            last = t;
        }
        if (a->a[i])
            a->a[i]->h = a;
    }
    return a;
}

Heap* a[MAXN];
Tree* ind[MAXN];

void change(int i, ll x) {
    Tree *t = ind[i];
    if (x < t->val) {
        t->val = x;
        //cout << ind[i] << endl;
        while (t->pr && (t->val < t->pr->val || (t->val == t->pr->val && t->index < t->pr->index))) {
            int j = t->pr->index;
            swap(t->val, t->pr->val);
            swap(ind[i], ind[j]);
            swap(t->index, t->pr->index);
            t = t->pr;
            //cout << ind[i] << endl;
        }
    } else {
        t->val = x;
        while (t->g.size()) {
            ll mn = LINF;
            int ind1 = -1;
            for (int j = 0; j < (int)t->g.size(); ++j) {
                if (t->g[j]->val < mn || (t->g[j]->val == mn && t->g[j]->index < ind1)) {
                    ind1 = j;
                    mn = t->g[j]->val;
                }
            }
            Tree* to = t->g[ind1];
            if (to->val > x || (to->val == x && to->index > i))
                break;
            int j = to->index;
            swap(t->val, to->val);
            swap(ind[i], ind[j]);
            swap(t->index, to->index);
            t = to;
        }
    }
}

void pop(Tree* t, Heap* &h) {
    Heap* h1 = new Heap();
    for (auto ch : t->g) {
        ch->pr = 0;
        h1 = merge(h1, new Heap(ch));
    }
    ind[t->index] = 0;
    h->a[t->rank] = 0;
    h = merge(h, h1);
}

void extractMin(Heap *h) {
    Tree* need = 0;
    ll mn = LINF;
    int j = INF;
    for (int i = 0; i < C; ++i) {
        Tree* t = h->a[i];
        if (!t)
            continue;
        if (t->val < mn || (t->val == mn && t->index < j)) {
            need = t;
            mn = t->val;
            j = i;
        }
    }
    pop(need, h);
}

void del(int i) {
    change(i, -LINF);
    Tree* t = ind[i];
    pop(t, t->h);
}


int main() {
    ios_base::sync_with_stdio(0);
    //freopen(TASK".in", "r", stdin); freopen(TASK".out", "w", stdout);
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int n, m;
    int cnt = 0;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        a[i] = new Heap();
        a[i]->Ind = i;
    }
    for (int q = 0; q < m; ++q) {
        int type;
        cin >> type;
        //cout << "*" << endl;
        if (type == 0) {
            ll x, to;
            cin >> to >> x;
            --to;
            Tree* t = new Tree(x, ++cnt);
            Heap* h = new Heap(t);
            ind[cnt] = t;
            //print(a[to]);
            a[to] = merge(a[to], h);
        }
        if (type == 1) {
            int x, y;
            cin >> x >> y;
            //print(a[x - 1]);
            //print(a[y - 1]);
            merge(a[y - 1], a[x - 1]);
            a[x - 1] = new Heap();
            a[x - 1]->Ind = x - 1;
        }
        if (type == 2) {
            int i;
            cin >> i;
            if (ind[i] == 0)
                continue;
            del(i);
        }
        if (type == 3) {
            int i, x;
            cin >> i >> x;
            change(i, x);
        }
        if (type == 4) {
            int x;
            cin >> x;
            cout << a[x - 1]->getMin() << "\n";
        }
        if (type == 5) {
            int i;
            cin >> i;
            //cout << a[0]->a[1]->index << endl;
            extractMin(a[i - 1]);
            //cout << a[0]->a[0]->index << endl;
        }
    }

    return 9/11;
}