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

int daddy[200001];
void init_daddy(int n) {
	for(int i=1; i<=n; i++)
		daddy[i] = i;
}

int find_daddy(int a) {
	if(daddy[a] == a) return a;
	return daddy[a] = find_daddy(daddy[a]);
}

inline bool query(int a, int b) {
	return find_daddy(a) == find_daddy(b);
}

inline void join(int a, int b) {
	daddy[find_daddy(a)] = find_daddy(b);
}

typedef struct muchie {
	int nod1, nod2, cost;
} muchie;

muchie muchii[400001];

bool sortare(muchie a, muchie b) {
	return a.cost < b.cost;
}

std::vector<int> sol;

int main() {
	FILE *fin = fopen("apm.in", "r"),
		*fout = fopen("apm.out", "w");

	unsigned int n, m, i;
	int a, b, c, cost_total = 0;
	fscanf(fin, "%u%u", &n, &m);
	init_daddy(n);

	for(i=0; i<m; i++) {
		fscanf(fin, "%d%d%d", &a, &b, &c);
		muchii[i].nod1 = a;
		muchii[i].nod2 = b;
		muchii[i].cost = c;
	}

	std::sort(muchii, muchii+m, sortare);

	for(i=0; sol.size() < n-1; i++) {
		if(query(muchii[i].nod1, muchii[i].nod2) == false) {
			sol.push_back(i);
			cost_total += muchii[i].cost;
			join(muchii[i].nod1, muchii[i].nod2);
		}
	}

	fprintf(fout, "%d\n%d\n", cost_total, n-1);
	for(unsigned int i=0; i<sol.size(); i++) {
		fprintf(fout, "%d %d\n", muchii[sol[i]].nod2, muchii[sol[i]].nod1);
	}

	fclose(fin);
	fclose(fout);
	return 0;	
}