#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;
vector <int> mult;
vector <muchie> muchii;
vector <muchie> arbore;

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

inline void add(int a, int b) {
	mult[a] = b;
}

int main(void) {
	ifstream fin("apm.in");
	fin >> n >> m;
	muchii.resize(m);
	mult.resize(n+1);
	arbore.reserve(n-1);
	for(int i = 0; i < m; ++i) 
		fin >> muchii[i].a >> muchii[i].b >> muchii[i].cost;
	fin.close();
	
	int rasp = 0;
	sort(muchii.begin(), muchii.end(), comp);
	for(int i = 1; i <=n; ++i)
		mult[i] = i;
	
	for(int i = 0; arbore.size() != n - 1; ++i) {
		if(find(muchii[i].a) != find(muchii[i].b)) {
			rasp += muchii[i].cost;
			add(muchii[i].a, muchii[i].b);
			arbore.push_back(muchii[i]);
		}
	}
	
	ofstream fout("apm.out");
	fout << rasp << '\n' << n - 1 << '\n';
	for(int i = 0; i < n - 1; ++i)
		fout << arbore[i].a << ' ' << arbore[i].b << '\n';
	fout.close();
}