#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fcin("mergeheap.in");
ofstream fcout("mergeheap.out");
struct HeapNode
{
	int val;
	HeapNode *leftChild, *brother;

	void addChild(HeapNode* src)
	{
		if (leftChild == NULL)
			leftChild = src;
		else {
			src->brother = leftChild;
			leftChild = src;
		}
	}

};

HeapNode* Merge(HeapNode* X, HeapNode* Y)
{
	if (X == NULL)
		return Y;
	if (Y == NULL)
		return X;
	// pentru a pastra proprietatea min heapului
	if (X->val > Y->val)
	{
		X->addChild(Y);
		return X;
	}
	else {
		Y->addChild(X);
		return Y;
	}
	return NULL;
}

HeapNode* Delete(HeapNode* node)
{
	if (node == NULL || node->brother == NULL)
		return node;
	else
	{
		HeapNode* X = node;
		HeapNode* Y = node->brother;
		HeapNode* newNode = node->brother->brother;

		X->brother = NULL;
		Y->brother = NULL;

		return Merge(Merge(X, Y), Delete(newNode));

	}
}

HeapNode* Insert(HeapNode* destination, int val)
{
	HeapNode* temp = new HeapNode();
	temp->val = val;
	return Merge(destination, temp);
}

class PairingHeap
{
public:
	HeapNode* root;
	PairingHeap() { root = NULL; }
	void Insert(int x) { root = ::Insert(root, x); }
	void Join(PairingHeap& ph) { root = Merge(root, ph.root); ph.root = NULL; }
	void Delete() { fcout << root->val << endl; root = ::Delete(root->leftChild); }
};

int main()
{
	int n, q, op, m, x, a, b;
	fcin >> n >> q;
	vector<PairingHeap> ph(n + 1);

	for (int i = 0; i < q; i++)
	{
		fcin >> op >> m;
		switch (op)
		{
		case 1:
			fcin >> x;
			ph[m].Insert(x);
			break;
		case 2:
			ph[m].Delete();
			break;
		case 3:
			fcin >> b;
			ph[m].Join(ph[b]);
		}
	}

	return 0;
}