#include <iostream>
#include <fstream>
#include <queue>
#include <limits>
#include <vector>

const int infinity = std::numeric_limits<int>::max();
const int dim = 200001;

bool inQ[dim];
int key[dim];
int parent[dim];
int noduri, muchii;
std::vector<std::pair<int, int>>G[dim];

struct cmp {
	bool operator()(int i, int j) {
		return key[i] > key[j];
	}
};

std::priority_queue<int, std::vector<int>, cmp>pq;

void input() {
	std::ifstream in("apm.in");
	in >> noduri >> muchii;
	for (int k = 1; k <= muchii; k++) {
		int i, j, cost;
		in >> i >> j >> cost;
		G[i].push_back(std::make_pair(j, cost));
		G[j].push_back(std::make_pair(i, cost));
	}
	pq.push(1);
	inQ[1] = true;
	for (int i = 2; i <= noduri; i++) {
		key[i] = infinity;
		pq.push(i);
		inQ[i] = true;
	}
}

int main() {

	input();
	int costTotal = 0;
	while (pq.empty() == false) {
		int min = pq.top();
		costTotal += key[min];
		pq.pop();
		inQ[min] = false;
		for (size_t y = 0; y < G[min].size(); y++) {
			int vecin = G[min][y].first;
			int cost = G[min][y].second;
			if (inQ[vecin] && cost < key[vecin]) {
				parent[vecin] = min;
				key[vecin] = cost;
			}
		}
	}

	std::ofstream out("apm.out");
	out << costTotal << "\n";
	out << noduri - 1 << "\n";
	for (int i = 2; i <= noduri; i++) {
		out << i << " " << parent[i] << "\n";
	}

	return 0;
}