#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin("mergeheap.in");
ofstream fout("mergeheap.out");

class Node {
public:
	int value;
	Node* parent;
	vector<Node*> children;
	int degree;

	Node(int value) {
		this->value = value;
		parent = nullptr;
		degree = 0;
		children.clear();
	}
};

class BinomialHeap {
public:
	vector<Node*> trees;
	Node* min_node;
	int total;

	BinomialHeap() {
		min_node = nullptr;
		total = 0;
		trees.clear();
	}

	bool isEmpty() {
		return min_node == nullptr;
	}

	void find_min() {
		min_node = nullptr;
		for (Node* tree : trees)
			if (min_node == nullptr || tree->value < min_node->value)
				min_node = tree;
	}

	void merge(BinomialHeap& other) {
		trees.insert(trees.end(), other.trees.begin(), other.trees.end());
		total += other.total;
		find_min();
		consolidate();
	}

	void insert(int x) {
		Node* nod = new Node(x);
		BinomialHeap heap;
		heap.trees.push_back(nod);
		merge(heap);
	}

	int extract_min() {
		Node* minNode = min_node;
		for (auto it = trees.begin(); it != trees.end(); it++)
			if (*it == minNode) {
				trees.erase(it);
				break;
			}
		BinomialHeap heap;
		heap.trees = minNode->children;
		merge(heap);
		find_min();
		total--;
		return minNode->value;
	}

	void link(Node* tree1, Node* tree2) {
		if (tree2->value < tree1->value)
			swap(tree1, tree2);
		tree2->parent = tree1;
		tree1->children.push_back(tree2);
		tree1->degree++;
	}

	void consolidate() {
		vector<Node*> degree_to_tree;
		while (!trees.empty()) {
			Node* crt = trees[0];
			trees.erase(trees.begin());
			int degree = crt->degree;
			while (degree >= int(degree_to_tree.size()))
				degree_to_tree.push_back(nullptr);
			while (degree_to_tree[degree] != nullptr) {
				Node* other = degree_to_tree[degree];
				degree_to_tree[degree] = nullptr;
				if (crt->value < other->value)
					link(crt, other);
				else {
					link(other, crt);
					crt = other;
				}
				degree++;
				while (degree >= int(degree_to_tree.size()))
					degree_to_tree.push_back(nullptr);
			}
			degree_to_tree[degree] = crt;
		}
		min_node = nullptr;
		trees.clear();
		for (Node* tree : degree_to_tree)
			if (tree != nullptr) {
				trees.push_back(tree);
				if (min_node == nullptr || tree->value < min_node->value)
					min_node = tree;
			}
	}
};

int main() {
	int n, q, op, x, a, b;
	vector<BinomialHeap> v;
	fin >> n >> q;
	for (int i = 0; i < n; i++)
		v.push_back(BinomialHeap());
	while (q--) {
		fin >> op;
		if (op == 1) {
			fin >> a >> x;
			v[a - 1].insert(-x);
		}
		else
			if (op == 2) {
				fin >> a;
				fout << -v[a - 1].extract_min() << "\n";
			}
			else {
				fin >> a >> b;
				v[a - 1].merge(v[b - 1]);
			}
	}
	return 0;
}