#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int NMAX = 200505;

struct edge {
	int from, to, cost;

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

int N, M, component[NMAX];
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());
	for (int i = 1; i <= N; i++) {
		component[i] = i;
	}

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

			int componentIdxToMove = component[candidate.to];
			for (int node = 1; node <= N; node++) {
				if (component[node] == componentIdxToMove) {
					component[node] = component[candidate.from];
				}
			}
		}
	}

	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;
}