#include <cstdio>
#include <cstdlib>

#define M 400001
#define N 200001

struct muchie { int x, y, c; };

int n, m;
muchie vm[M];
int sel[N];

int cost_apm = 0;

int tata[N], rang[N];

void init_disjoint()
{
	for(int i = 1; i <= n; ++i) 
	{
		tata[i] = i;
		rang[i] = 1;
	}
}

int radacina(int x)
{
	int rez = x, aux;
	
	while(tata[rez] != rez) rez = tata[rez];
	
	while(tata[x] != x)
	{
		aux = tata[x];
		tata[x] = rez;
		x = tata[x];
	}
	
	return rez;
}

void reuneste(int x, int y)
{
	if(rang[x] > rang[y]) tata[y] = x;
	else tata[x] = y;
	
	if(rang[x] == rang[y]) rang[y]++;
}

int fcmp(const void* a, const void* b)
{
	muchie ma = *((muchie*)a);
	muchie mb = *((muchie*)b);
	
	return ma.c - mb.c;
}

void sortare()
{
	qsort(vm, m, sizeof(vm[0]), fcmp);
}

void kruskal()
{
	sortare();
	init_disjoint();
	int index_vm = 0;
	for(int i = 0; i < n-1; ++i)
	{
		//completez sel[i] cu indicele muchiei pe care o aleg din vm
		while(radacina(vm[index_vm].x) == radacina(vm[index_vm].y)) ++index_vm;
		sel[i] = index_vm;
		cost_apm += vm[index_vm].c;
		reuneste(vm[index_vm].x, vm[index_vm].y);
	}		
}

void citeste()
{
	scanf("%d%d", &n, &m);
	int i;
	for(i = 0; i < m; ++i) scanf("%d%d%d", &vm[i].x, &vm[i].y, &vm[i].c);
}

void scrie()
{
	printf("%d\n%d\n", cost_apm, n-1);
	int i;
	for(i = 0; i < n-1; ++i) printf("%d %d\n", vm[sel[i]].x, vm[sel[i]].y);
}

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	citeste();
	kruskal();
	scrie();
	return 0;
}