#include <fstream>
#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) {
	ifstream fin("apm.in");
	fin >> n >> m;
	
	for(int i = 0; i < m; ++i) 
		fin >> muchii[i].a >> muchii[i].b >> muchii[i].cost;
	fin.close();
	
	int rasp = 0;
	sort(muchii, muchii + m, comp);
	for(int i = 1; i <= n; ++i) {
		mult[i] = i;
		adanc[i] = 0;
	}
	
	for(int i = 0, ind = 0; ind < n - 1; ++i) {
		if(find(muchii[i].a) != find(muchii[i].b)) {
			rasp += muchii[i].cost;
			add(muchii[i].a, muchii[i].b);
			arbore[ind++] = i;
		}
	}
	
	ofstream fout("apm.out");
	fout << rasp << '\n' << n - 1 << '\n';
	for(int i = 0; i < n - 1; ++i)
		fout << muchii[arbore[i]].a << ' ' << muchii[arbore[i]].b << '\n';
	fout.close();
}