#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <ctime>
#include <string>
#include <algorithm>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <stack>
#define pb push_back
#define mp make_pair
#define mt make_triple
#define For(i,a,b) for (i = a; i <= b; ++i)
#define oo (1<<30)
#define FIN "radiatie.in"
#define FOUT "radiatie.out"
#define N 15010
using namespace std;
struct triplet {	int first,second,third;  }; 
vector<triplet> Muchie;
triplet make_triple(int a,int b,int c){	triplet x;	x = (triplet) { a, b, c};	return x;}
inline bool cmp(triplet a,triplet b){	return a.third < b.third; }
int n,m,k;
int par[N];
vector<int> Cine[N],Cost[N];
bool dif_comp(int x, int y) {
	int p1 = x, p2 = y;
	while (par[p1] != p1)
		p1 = par[p1];
	while (par[p2] != p2) 
		p2 = par[p2];
	
	if (p1 != p2) 	return true;
	else 			return false;
}

void merge_comp(int x, int y) {
	int p1 = x, p2 = y, ant, pp;
	while (par[p1] != p1) 
		p1 = par[p1];
	pp = p1;p1 = x;
	while (par[p1] != pp) {
		ant = p1;
		p1 = par[p1];
		par[ant] = pp;
	}
	while (par[p2] != pp) {
		ant = p2;
		p2 = par[p2];
		par[ant] = pp;
	}
}

void APM() {
	int i, ant, p, pp;
	for (i = 1; i <= n; ++i)
		par[i] = i;
	for (i = 0; i < m; ++i) {
		if (dif_comp(Muchie[i].first, Muchie[i].second)) {
			Cine[Muchie[i].first].push_back(Muchie[i].second);
			Cost[Muchie[i].first].push_back(Muchie[i].third);
			Cine[Muchie[i].second].push_back(Muchie[i].first);
			Cost[Muchie[i].second].push_back(Muchie[i].third);
			merge_comp(Muchie[i].first, Muchie[i].second);
		}
	}	
	for (i = 1; i <= n; ++i)
		if (par[i] == i) {
			Cine[i].push_back(0);
			Cine[0].push_back(i);
			Cost[0].push_back(0);
			Cost[i].push_back(0);
			par[i] = 0;
		}
}
int tata[N];
int Euler[M],Lev[M];
void df(int x,int level,int father){
	viz [x] = 1;
	Level[x] = level;
	Euler[ ++ nr] = x;
	Lev  [ ++ nr] = level;
	tata[x] = father;
	int i;
	for (i = 0; i < Cine[x].size(); ++i){
		if (!viz[Cine[x][i]){
			df(Cine[x][i],x);
			Euler[ ++ nr] = x;
			Lev  [ ++ nr] = level;
		}
}
void RmqBuild(){
}
int main(){
	int a,b,c,i,j;
	freopen(FIN,"r",stdin);
	freopen(FOUT,"w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for (i = 1; i <= m; ++i){
		scanf("%d%d%d",&a,&b,&c);
		Muchie.pb(mt(a,b,c));
	}
	sort(Muchie.begin(), Muchie.end(), cmp);
	APM();
	for (i = 1; i <= n; ++i){
		for (j = 0; j < Cine[i].size(); ++j)
			printf("(%d %d) ",Cine[i][j],Cost[i][j]);
		puts("");
	}
	df(0,0,0);
}