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

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

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

int n, m;
int mult[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) {
	mult[find(a)] = find(b);
}

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;
	
	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();
}