#include <stdio.h>
#include <stdlib.h>

#define MAX_M	100000
#define MAX_N	1000

typedef struct{
	int from;
	int to;
	int length;
}T_EDGE;
	
int ud[MAX_N];	/* Ukazatelé na nadřízené vrcholy */
int vn[MAX_N];	/* Velikosti podřízených komponent */
T_EDGE h[MAX_M];

/* Nalezne šéfa komponenty a přepíše odkazy na nadřízené */
int find_chief(int a)
{
	int h, x=a;

	while (ud[a]!=a)
		a=ud[a];
	while (ud[x]!=x){
		h=ud[x];
		ud[x]=a;
		x=h;
	}
	return a;
}

/* Spojí dvě komponenty */
void join(int a, int b)
{
	a=find_chief(a);
	b=find_chief(b);
	if (vn[a] < vn[b]) {
		vn[b]+=vn[a];
		ud[a]=b;
	}
	else {
		vn[a]+=vn[b];
		ud[b]=a;
	}
}

int cmp(const void *a, const void *b)
{
	return ((T_EDGE *)a)->length - ((T_EDGE *)b)->length;
}

int main(void)
{
	int i, n, m, no_edge, sum; 

	/* Inicializace */
	for (i=0; i<MAX_N; i++){
		ud[i]=i;
		vn[i]=1;
	}
	
	scanf("%d %d", &n, &m);
	for (i=0; i<m; i++){
		scanf("%d %d %d", &h[i].from, &h[i].to, &h[i].length);
	}
	
	/* Setřídíme si hrany podle délky */
	qsort(h, m, sizeof(T_EDGE), cmp);

	no_edge=0;
	i=0;
	sum=0;
	while (no_edge<n-1){	/* Ještě nemáme dost hran? */
		/* Vrcholy v různých komponentách? */
		if (find_chief(h[i].from) != find_chief(h[i].to)){
			/* Přidáme hranu, spojíme komponenty */
			join(h[i].from, h[i].to);
			printf("Udrzuj cestu z %d do %d\n", h[i].from, h[i].to);
			sum+=h[i].length;
			no_edge++;
		}
		i++;
	}
	printf("Celkove se musi udrzovat %d km silnic.\n", sum);
	
	return 0;
}