#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n, m;
int const maxim = 10000;
struct compara {
	bool operator()(pair<int,int> x, pair<int,int> y) {
		return x.second > y.second;
	}
};
vector<pair<int, int>> stocare[maxim];
priority_queue<pair<int, int>, vector<pair<int, int>>, compara> coada;
int copil[maxim] = { 0 };

void prim(int nodstart) {
	//initiaalizam toate nodurile ca fiind nevizitate si ca neavand tati
	bool vizitat[maxim] = {false};
	int cost_arbore = 0;
	//nodul de start il marcam ca si vizitat
	vizitat[nodstart] = true;
	copil[nodstart] = 0;
	int nodcurent = nodstart;
	for (int i = 1; i <= n - 1; i++) {
		//adaugam in coada toate muchiile care pornesc din nodul curent
		for (auto x : stocare[nodcurent]) {
			coada.push(x);
		}
		//scoatem primul nod din coada
		pair<int, int> aux = coada.top();
		coada.pop();
		//in caz ca nodul care formeaza muchia se afla deja in arbore, eliminam muchia din coada si alegem o alta muchie
		while (vizitat[aux.first]) {
			aux = coada.top();
			coada.pop();
		}
		//daca nodul nu se afla in arbore, il marcam ca si vizitat acum si ii stabilim tatal 
		vizitat[aux.first] = true;
		copil[nodcurent] = aux.first;
		//marim costul arborelui
		cost_arbore += aux.second;
		nodcurent = aux.first;
	}
	out << cost_arbore << endl;
}

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 afisare(int nodstart) {
	out << n - 1 << endl;
	int nod = nodstart;
	while (copil[nod] != 0) {
		out << nod << " " << copil[nod] << endl;
		nod = copil[nod];
	}
}


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