#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct muchie {
	int nod, cost;
};

struct muchieKruski {
	int capatA, capatB, cost;

	bool operator<(const muchieKruski& temp) const
	{
		return cost < temp.cost;
	}
};

int n, m, q;

vector<muchieKruski> muchii;
vector<vector<muchie>> adj;

vector<int> parent, rang;

int find(int x)
{
	int repX;
	for (repX = x; repX != parent[repX]; repX = parent[repX]);

	int reprezentant = repX;
	for (repX = x; repX != parent[repX]; repX = parent[repX])
	{
		parent[repX] = reprezentant;
	}

	return repX;
}

void marea_unire(int x, int y)
{
	int repX = find(x);
	int repY = find(y);

	if (repX == repY) return;

	//compar in functie de inaltime
	if (rang[repX] > rang[repY])
		parent[repY] = repX;
	else if (rang[repX] < rang[repY])
		parent[repX] = repY;
	else
	{
		parent[repY] = repX;
		rang[repX]++;
	}
}

int main() {
	cin >> n >> m >> q;
	adj.resize(n + 1);
	parent.resize(n + 1);
	rang.resize(n + 1, 1);
	muchii.resize(m + 1);
	for (int i = 1; i <= m; i++)
	{
		int x, y, cost;
		cin >> x >> y >> cost;
		muchii[i] = {x, y ,cost};
	}

	sort(muchii.begin() + 1, muchii.begin() + m + 1);
	cout << "\n\n";
	for (int i = 1; i <= m;i++) cout << muchii[i].capatA << " " << muchii[i].capatB << " " << muchii[i].cost << '\n';
	cout << "\n\n";

	for (int i = 1; i <= n; i++)
	{
		parent[i] = i;
	}

	for (int i = 1; i <= m; i++)
	{
		int capat1 = find(muchii[i].capatA);
		int capat2 = find(muchii[i].capatB);
		int cost = muchii[i].cost;
		if (capat1 != capat2)
		{
			cout << capat1 << " " << capat2 << "\n";
			adj[muchii[i].capatA].push_back({ muchii[i].capatB, cost });
			adj[muchii[i].capatB].push_back({ muchii[i].capatA, cost });
			marea_unire(muchii[i].capatA, muchii[i].capatB);
		}
	}

	for (int i = 1; i <= n; i++)
	{
		cout << i << " : ";
		for (auto e : adj[i]) cout << e.nod << " " << e.cost << "   ";
		cout << '\n';

	}

	//de continuat
}