#include <stdio.h>
#include <stack>
#include <vector>
#include <algorithm>

#define NMAX 200001
#define MMAX 400001

using namespace std;

struct edge {
	int x, y;
	int weight;
} edges[MMAX];

int parent[NMAX], rang[NMAX];
int n, m;
vector< pair<int, int> > sol;

bool cmp(edge first, edge second) {
	return first.weight < second.weight;
}

int findSet(int x) {
	int i = x;
	while(parent[i] != i) {
		i = parent[i];
	}
	int j = x, aux;
	while (parent[j] != j) {
		aux = parent[j];
		parent[j] = i;
		j = aux;
	}
	return i;
}

void unite(int x, int y) {
	if (rang[x] > rang[y]) {
		parent[y] = x;
	} else {
		parent[x] = y;
	}

	if (rang[x] == rang[y]) {
		++ rang[y];
	}
}

long long kruskal(int root) {
	long long weight = 0;
	for (int i = 1; i <= n; ++ i) {
		rang[i] = 1; parent[i] = i;
	}
	for (int i = 1; i <= m; ++ i) {
		int X, Y;
		if ((X = findSet(edges[i].x)) != (Y = findSet(edges[i].y))) {
			sol.push_back(make_pair(edges[i].x, edges[i].y));
			weight += edges[i].weight;
			unite(X, Y);
		}
	}
	return weight;
}

int main() {
	FILE *in, *out;
	in = fopen("apm.in", "r");
	out = fopen("apm.out", "w");
	int a, b;
	fscanf(in, "%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		fscanf(in, "%d%d%d", &edges[i].x, &edges[i].y, &edges[i].weight);
	}
	sort(edges + 1, edges + m + 1, cmp);
	fprintf(out, "%lld\n", kruskal(1));
	fprintf(out, "%d\n", (int)sol.size());
	for (int i = 0; i < sol.size(); ++i) {
		fprintf(out, "%d %d\n", sol[i].first, sol[i].second);
	}
}