#pragma GCC optimize("Ofast")
#define NDEBUG

#include <vector>
#include <cstdint>
#include <cassert>
#include <string>
#include <algorithm>

namespace ja::AdvancedDataStructures::FibonacciHeap {
	#ifndef jassert
		#define jassert(expr, msg, ...) assert(expr && msg)
	#endif // jassert
	#ifndef jlog
		#define jlog(...) ((void)0)
	#endif // jlog

	template < typename DATA, typename OPS >
	class FibonacciHeap {
	public:
		struct Node { // This has to be public, since it's also the index for decrease_key()
			DATA key; int32_t degree; bool mark;
			Node *left, *right, *parent, *child;

			Node(const DATA& _value) {
				key = _value; degree = 0; mark = false;
				left = right = this;
				parent = child = nullptr;
			}
		};

	private:
		Node *heap_min;
		size_t node_count;
		OPS op{};

		void _erase(Node *a) {
			if(a == nullptr) return;

			for(Node *b = a->right; b != a;) {
				_erase(b->child);
				Node *next_b = b->right;
				delete b;
				b = next_b;
			}
			_erase(a->child); delete a;
		}

		Node* _merge(Node *a, Node *b) {
			if(a == nullptr || b == nullptr) return (a ? a : b);

			if( op.less(b->key, a->key) ) std::swap(a, b); // Make sure you have to merge b into a (a remains heap_min)

			// Connect the two circular lists
			Node *a_right = a->right, *b_left = b->left;
			a->right = b; b->left = a;
			a_right->left = b_left; b_left->right = a_right;

			return a;
		}

		void _extract_from_circular_list(Node *node) {
			if(node->right == node) return;

			Node *l = node->left, *r = node->right;
			l->right = r; r->left = l;
			node->left = node->right = node;
		}

		void _insert_node(Node *new_node) {
			heap_min = _merge(heap_min, new_node);
		}


		void _remove_parents_from_circular_list(Node *node) {
			if(node == nullptr) return; // there is no element in the circular list

			Node *oth = node;
			do { oth->parent = nullptr; oth = oth->right; } while(oth != node);
		}

		Node* _add_child(Node *parent, Node *child) {
			if( op.less(child->key, parent->key) ) std::swap(parent, child);

			parent->degree += 1;

			parent->child = _merge(parent->child, child);
			child->parent = parent;

			return parent;
		}

		DATA _get_min() {
			return heap_min->key;
		}

		void _consolidate() {
			const int MAX_DEGREE = 24; int max_degree = 0;
			static Node* root_by_degree[MAX_DEGREE] = {nullptr,};

			if(heap_min == nullptr) return; // nothing to consolidate

			Node *to_consolidate;
			bool more_to_consolidate = true;
			do {
				to_consolidate = heap_min->right;
				_extract_from_circular_list(to_consolidate);

				if(to_consolidate == heap_min) more_to_consolidate = false;

				for(int deg = to_consolidate->degree; deg < MAX_DEGREE; deg += 1) {
					if(deg > max_degree) max_degree = deg;

					if(root_by_degree[deg] == nullptr) {
						root_by_degree[deg] = to_consolidate;
						break;
					}
					else {
						to_consolidate = _add_child(to_consolidate, root_by_degree[deg]);
						root_by_degree[deg] = nullptr;
					}
				}
			} while(more_to_consolidate);

			heap_min = nullptr;
			for(int deg = max_degree; deg >= 0; deg -= 1) {
				heap_min = _merge(heap_min, root_by_degree[deg]);
				root_by_degree[deg] = nullptr;
			}
		}

		void _pop_min() {
			if(heap_min->right == heap_min) { // |Roots| has one element, special case
				Node *new_heap_min = heap_min->child;

				_remove_parents_from_circular_list(heap_min->child);
				delete heap_min;

				heap_min = new_heap_min;
				return;
			}

			Node *heap_min_children = heap_min->child;
			Node *new_heap_min = heap_min->right;

			// break links to other nodes on its level
			_extract_from_circular_list(heap_min);
			// before deleting
			delete heap_min;

			_remove_parents_from_circular_list(heap_min_children);
			heap_min = _merge(new_heap_min, heap_min_children);

			_consolidate();
		}

		void _cut(Node *node) {
			node->mark = false; // Mark it, since it has been cut

			// Break links to parent and siblings
			if(node->right == node) node->parent->child = nullptr;
			else node->parent->child = node->right;

			node->parent->degree -= 1;

			_extract_from_circular_list(node);
			node->parent = nullptr;

			// Add it to |Roots|
			heap_min = _merge(heap_min, node);
		}

		void _cascut(Node *node) { // cascading cut
			if(node->parent == nullptr) {
				node->mark = false;
				return;
			}

			if(node->mark == false) {
				node->mark = true;
			}
			else {
				Node *parent = node->parent;
				_cut(node); _cascut(parent);
			}
		}

		void _decrease_key(Node *node, const DATA& new_key) {
			node->key = new_key;

			if(node->parent == nullptr) {
				if( op.less(node->key, heap_min->key) ) heap_min = node;
			}
			else {
				Node *parent = node->parent;
				_cut(node); _cascut(parent);
			}
		}

	public:
		struct Iterator {
			// private:
			Node *node_ptr;

			// public:
			Iterator() { node_ptr = nullptr; }
			Iterator(Node *_node_ptr) { node_ptr = _node_ptr; }

			DATA value() { return node_ptr->key; }
		};

		FibonacciHeap() {
			heap_min = nullptr; node_count = 0;
		}

		void clear() { node_count = 0; _erase(heap_min); heap_min = nullptr; }
		size_t size() { return node_count; }

		Iterator insert(const DATA &v) {
			node_count += 1;

			Node *v_node = new Node(v);
			heap_min = _merge(heap_min, v_node);
			return Iterator(v_node);
		}

		DATA get_min() {
			jassert(heap_min != nullptr, "heap must not be empty", heap_min);
			return _get_min();
		}

		void pop_min() {
			jassert(heap_min != nullptr, "heap must not be empty", heap_min);
			node_count -= 1; _pop_min();
		}

		void decrease_key(Iterator it, const DATA& new_key) {
			jassert( !op.less(it.value(), new_key), "New key must be less than old key", new_key, it.value());
			_decrease_key(it.node_ptr, new_key);
		}

		void decrease_key_if_smaller(Iterator it, const DATA& new_key) {
			if( op.less(new_key, it.node_ptr->key) ) _decrease_key(it.node_ptr, new_key);
		}

		void erase(Iterator it) {
			jassert(heap_min != nullptr, "heap must not be empty", heap_min);

			node_count -= 1;

			_decrease_key(it.node_ptr, op.min());
			_pop_min();
		}

		void join(FibonacciHeap& oth) {
			node_count += oth.node_count;
			heap_min = _merge(heap_min, oth.heap_min);

			oth.heap_min = nullptr; oth.node_count = 0;
		}
	};
};

#include <bits/stdc++.h>

using namespace std;

#ifdef INFOARENA
ifstream in("mergeheap.in");
ofstream out("mergeheap.out");
#define cin in
#define cout out
#endif // INFOARENA

struct ops {
	int32_t min() { return -1e9; }
	bool less(int32_t a, int32_t b) { return a > b; }
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, q; cin >> n >> q;
	vector<ja::AdvancedDataStructures::FibonacciHeap::FibonacciHeap<int32_t, ops>> v(n + 1);

	for(int i = 0; i < q; i++) {
		int t; cin >> t;
		if(t == 1) {
			int m, x; cin >> m >> x;
			v[m].insert(x);
		}
		if(t == 2) {
			int m; cin >> m;
			cout << v[m].get_min() << '\n';
			v[m].pop_min();
		}
		if(t == 3) {
			int a, b; cin >> a >> b;
			v[a].join(v[b]);
		}
	}
}