#include <fstream>
#include <queue>
#include <vector>
#include <functional>

using namespace std;


int main() {
	ifstream cin("apm.in");
	ofstream cout("apm.out");
	int N, M;
	int a, b, c, v;
	cin >> N >> M;
	int cost = 0;
	vector< vector< pair<int, int> > > graph(N);;
	vector< pair<int, int> > ans(N - 1);
	vector<int> best(N, int(1e9));
	vector<int> parent(N);
	priority_queue< pair<int, int> > q;
	vector<bool> visited(N);
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		a--, b--;
		graph[a].push_back({ b, c });
		graph[b].push_back({ a, c });
	}
	
	best[0] = 0;
	q.push({ 0, 0 });
	for (int step = 1; step <= N; step++) {

		do {
			tie(c, v) = q.top();
			q.pop();
		} while (!q.empty() && visited[v]);

		visited[v] = 1;
		if (step > 1) {
			ans[step - 2] = { parent[v], v };
			cost += -c;
		}

		for (auto& w : graph[v]) {
			if (!visited[w.first] && best[w.first] > w.second) {
				best[w.first] = w.second;
				parent[w.first] = v;
				q.push({ -w.second, w.first });
			}
		}
	}

	cout << cost << "\n";
	cout << N - 1 << "\n";
	for (auto& p : ans) {
		cout << p.first + 1 << " " << p.second + 1 << "\n";
	}

	return 0;
}