#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct edge {
	int from, to, cost;

	bool operator < (const edge& other) const {
		return cost < other.cost;
	}
};

int N, M;
vector<edge> allEdges;

void read() {
	scanf("%d%d", &N, &M);
	int x, y, cost;
	for (int edgeIdx = 0; edgeIdx < M; edgeIdx++) {
		scanf("%d%d%d", &x, &y, &cost);
		allEdges.push_back({x, y, cost});
	}
}

void solve() {
	sort(allEdges.begin(), allEdges.end());
	vector<vector<int>> components(N + 1);
	vector<int> whatComponent(N + 1);

	for (int i = 1; i <= N; i++) {
		whatComponent[i] = i - 1;
		components[i - 1].push_back(i);
	}

	int result = 0;
	vector<edge> sol;
	for (edge& candidate : allEdges) {
		if 	(whatComponent[candidate.from] != whatComponent[candidate.to]) {
			result += candidate.cost;
			sol.push_back(candidate);

			int smallerComponent, largerComponent;
			if (components[whatComponent[candidate.from]].size() < components[whatComponent[candidate.to]].size()) {
				smallerComponent = whatComponent[candidate.from];
				largerComponent = whatComponent[candidate.to];
			} else {
				smallerComponent = whatComponent[candidate.to];
				largerComponent = whatComponent[candidate.from];
			}

			for (auto& node : components[smallerComponent]) {
				whatComponent[node] = largerComponent;
				components[largerComponent].push_back(node);
			}
			components[smallerComponent].clear();
		}
	}

	printf("%d\n", result);
	printf("%d\n", (int) sol.size());
	for (edge& usedEdge : sol) {
		printf("%d %d\n", usedEdge.from, usedEdge.to);
	}
}

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	read();
	solve();
	return 0;
}