#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int const maxim = 200005;
int n, m;

struct muchie {
	int nodstart;
	int nodfinish;
	int cost;
};

struct compara {
	bool operator()(muchie x, muchie y) {
		return x.cost > y.cost;
	}
};

priority_queue<muchie, vector<muchie>, compara> coada;
vector< pair<int, int> > stocare[maxim];
vector<muchie> muchii;


void citire() {
	in >> n >> m;
	int a, b, c;
	for (int i = 1; i <= m; i++) {
		in >> a >> b >> c;
		stocare[a].push_back(make_pair(b, c));
		stocare[b].push_back(make_pair(a, c));
	}
}

void prim(int nodstart) {
	int nodcurent = nodstart;
	int cost_arbore = 0;
	bool vizitat[maxim] = { false };
	vizitat[nodcurent] = true;
	for (int i = 1; i <= n - 1; i++) {
		for (auto x : stocare[nodcurent]) {
			coada.push({ nodcurent,x.first,x.second });
		}
		muchie aux = coada.top();
		coada.pop();
		while (vizitat[aux.nodfinish]) {
			aux = coada.top();
			coada.pop();
		}
		vizitat[aux.nodfinish] = true;
		nodcurent = aux.nodfinish;
		cost_arbore += aux.cost;
		muchii.push_back(aux);
	}
	out << cost_arbore << endl;
}

void afisare() {
	out << n - 1 << endl;
	for (auto x : muchii) {
		out << x.nodstart << " " << x.nodfinish << endl;
	}
}

int main() {
	citire();
	prim(1);
	afisare();
	return 0;
}