#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

struct muchie {
	int a, b;
	int cost;
};

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

int n, m;
int mult[200001];
int adanc[200001];
muchie muchii[400001];
int arbore[200001];

int find(int nod) {
	if(mult[nod] != nod)
		mult[nod] = find(mult[nod]);
	return mult[nod];
}

inline void add(int a, int b) {
	int rada = find(a);
	int radb = find(b);
	if(adanc[rada] > adanc[radb]) 
		mult[radb] = mult[rada];
	else if(adanc[rada] < adanc[radb])
		mult[rada] = mult[radb];
	else {
		mult[rada] = mult[radb];
		adanc[radb]++;
	}
}

int main(void) {
	freopen("apm.in", "r", stdin);
    scanf("%d %d", &n, &m);
	for(int i = 0; i < m; ++i) 
		scanf("%d %d %d", &muchii[i].a, &muchii[i].b, &muchii[i].cost);
	
	int rasp = 0;
	sort(muchii, muchii + m, comp);
	for(int i = 1; i <= n; ++i) {
		mult[i] = i;
		adanc[i] = 0;
	}
	
	int ind = 0;
	for(int i = 0; i < m; ++i) {
		if(find(muchii[i].a) != find(muchii[i].b)) {
			rasp += muchii[i].cost;
			add(muchii[i].a, muchii[i].b);
			arbore[ind++] = i;
		}
	}
	freopen("apm.out", "w", stdout);
    printf("%d\n%d\n", rasp, ind);
	for(int i = 0; i < ind; ++i)
		printf("%d %d\n", muchii[arbore[i]].a, muchii[arbore[i]].b);
}