#include <iostream>
#include <vector>
#include <fstream>
#include <set>
#include <algorithm>
using namespace std;
int main() {

	/*
	Input: 
	[Numar Noduri]
	[Nod1] [Nod2] [Pondere]
	*/
	vector<pair<int, int> > graf;
	int ponderi[10][10];
	
	vector<pair<int, int> > apcm;
	int papcm[10][10];
	ifstream f("apm.in");
	ofstream f1("apm.out");
	int n, a, b, c,d;
	f >> n>>d;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			ponderi[i][j] = -1;
			papcm[i][j] = -1;
		}
	}
	while (f >> a >> b >> c) {
		graf.push_back(make_pair(a-1, b-1));
		ponderi[a - 1][b - 1] = c;
		ponderi[b - 1][a - 1] = c;

	}

	vector<set<int> > sets(n);

	for (int i = 0; i <n;i++) {
		sets[i].insert(i);
	}
	int cost=0;
	//[&](auto fir, auto sec) {int i = ponderi[fir.first][fir.second], j = ponderi[sec.first][sec.second]; return i < j; }
	//Asta e o expresie lambda, basically o functie anonima, se poate inlocui cu o functie ca la qsort de la C
	sort(graf.begin(), graf.end(), [&](pair<int, int> fir, pair<int, int> sec) {int i = ponderi[fir.first][fir.second], j = ponderi[sec.first][sec.second]; return i < j; });
	for (pair<int, int> a : graf) {
		if (sets[a.first] != sets[a.second]) {
			apcm.push_back(a);
			cost+=ponderi[a.first][a.second];
			set<int> _temp;
			for (int i : sets[a.first]) _temp.insert(i);
			for (int i : sets[a.second]) _temp.insert(i);
			for(int a : _temp)
				sets[a] = _temp;
			papcm[a.first][a.second] = papcm[a.second][a.first] = ponderi[a.second][a.first];
		}
	}
	f1<<cost<<endl<<apcm.size()<<endl;

	for (pair<int, int> a : apcm) {
		f1<< a.first+1 << " " << a.second+1<< endl;
	}

	return 0;
}