#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

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

int n, m, S;
vector <Muchie> graf, sol;
vector <int> tata, nivel;

bool Compara(Muchie a, Muchie b) {
	return (a.c < b.c);
}

int Find(int x) {
	if(tata[x] == x) return x;
	else tata[x] = Find(tata[x]);
	
	return tata[x];
}

void Merge(int x, int y, int c) {
	int tataX = Find(x); // tatal lui x
	int tataY = Find(y); // tatal lui y
	
	if(tataX == tataY) return;
	
	sol.push_back((Muchie){x, y, c});
	S += c;
	
	if(nivel[tataX] < nivel[tataY]) tata[tataX] = tataY;
	else if(nivel[tataX] > nivel[tataY]) tata[tataY] = tataX;
	else {
		tata[tataY] = tataX;
		nivel[tataX]++;
	}
}

int main() {
	int i, x, y, c;
	
	freopen("amp.in", "r", stdin), freopen("apm.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for(i = 1; i <= m; i++) {
		scanf("%d %d %d", &x, &y, &c);
		graf.push_back((Muchie){x, y, c});
	}

	sort(graf.begin(), graf.end(), Compara); // sortez muchiile crescator dupa cost
	
	tata.push_back(0);
	nivel.assign(n + 1, 1); // nivel[i] = 1
	for(i = 1; i <= n; i++) tata.push_back(i); // tata[i] = i	
	for(i = 0; i < (int)graf.size(); i++) Merge(graf[i].x, graf[i].y, graf[i].c);
	
	printf("%d\n%d\n", S, sol.size());
	for(i = 0; i < (int)sol.size(); i++) printf("%d %d\n", sol[i].x, sol[i].y);
	
	return 0;
}