#include <fstream>
#include <vector>
#include <set>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int main() {

	int n, m;
	f >> n >> m;
	
	vector < vector< pair<int, int>>> G(n + 1);
	vector <int> viz(n + 1, 0);
	vector <int> cost(n + 1, 1 << 25);
	vector <int> tata(n + 1, 0);
	set < pair<int, int>> S;
	S.insert(make_pair(0, 1));
	viz[1] = 1;
	cost[1] = 0;

	for (int i = 0; i < m; i++) {
		int x, y, cost;
		f >> x >> y >> cost;
		G[x].push_back(make_pair(cost, y));
		G[y].push_back(make_pair(cost, x));
	}

	while (!S.empty()) {
		int nodCurent = (*S.begin()).second;
		int costCurent = (*S.begin()).first;
		viz[nodCurent] = 1;
		S.erase(S.begin());
		for (auto nod : G[nodCurent]) {
			if (viz[nod.second] == 0) {
				if (cost[nod.second] > nod.first) {
					cost[nod.second] = nod.first;
					S.insert(make_pair(cost[nod.second], nod.second));
					tata[nod.second] = nodCurent;
				}
			}
		}
	}

	int costTotal = 0;
	for (int i = 1; i <= n; i++) costTotal += cost[i];
	g << costTotal << '\n';
	g << n - 1 << '\n';
	for (int i = 2; i <= n; i++) g << i << ' ' << tata[i] << '\n';
	return 0;
}