#include<cstdio>
#include<algorithm>

struct muchie {
	int nod1, nod2, cost;
	bool in_solutie;
};

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

muchie muchii[400001];
int t[200001];

int tata(int nod) {
	if(nod == t[nod]) return nod;
	return t[nod] = tata(t[nod]);
}

void join(int a, int b) {
	t[tata(a)] = tata(b);
}

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

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

	fscanf(fin, "%d%d", &n, &m);
	for(int i=1;i<=n;i++) t[i]=i;
	for(int i=1;i<=m;i++)
		fscanf(fin, "%d%d%d", &muchii[i].nod1, &muchii[i].nod2, &muchii[i].cost);

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

	int cost_minim = 0;
	for(int nr=0, i=1; i<=m && nr < n-1; i++) {
		if(!query(muchii[i].nod1, muchii[i].nod2)) {
			join(muchii[i].nod1, muchii[i].nod2);
			nr++;
			cost_minim += muchii[i].cost;
			muchii[i].in_solutie = true;
		}
	}

	fprintf(fout, "%d\n%d\n", cost_minim, n-1);
	for(int i=1; i<=m; i++) {
		if(muchii[i].in_solutie) fprintf(fout, "%d %d\n", muchii[i].nod1, muchii[i].nod2);
	}
}