#include<stdio.h>
#include<algorithm>

#define M 400003
#define N 200003

using namespace std;

int n, m, nr, x, y, tata[N], cost, h[N];
struct muchie{int x, y, z;} a[M], q[N];

void citire(), rezolva(), afisare();
bool cmp(int xx, int yy){
	return (a[xx].z < a[yy].z);
}

int main(){
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	citire();
	rezolva();
	afisare();

	return 0;
}

void citire(){
	scanf("%d %d" , &n, &m);
	for (int i = 1; i <= m; i++){
		scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
		h[i] = i;
	}
	sort(h+1, h+m+1, cmp);
}

void rezolva(){
int nr1, nr2;
	for (int i = 1; i <= m; i++){
		for (x = a[h[i]].x, nr1 = 0; tata[x] != 0; x = tata[x], nr1++);
		for (y = a[h[i]].y, nr2 = 0; tata[y] != 0; y = tata[y], nr2++);
		if (x != y){
			if (nr1 < nr2) tata[x] = y;
			else	tata[y] = x;
			q[++nr].x = a[h[i]].x;
			q[nr].y = a[h[i]].y;
			cost += a[h[i]].z;
		}
	}
}

void afisare(){
	printf("%d\n%d\n", cost, n-1);
	for (int i = 1; i <= nr; i++){
		printf("%d %d\n", q[i].x, q[i].y);
	}

}