#include <stdio.h>
#include <stdlib.h>

struct edge {
	int x, y, cost;
} V[400005], Apm[400005], edge;


int Dad[200005], Rank[200005], size;

void Swap(int i, int j) {
	int tmp = V[i].x;
	V[i].x = V[j].x;
	V[j].x = tmp;
	tmp = V[i].y;
	V[i].y = V[j].y;
	V[j].y = tmp;
	tmp = V[i].cost;
	V[i].cost = V[j].cost;
	V[j].cost = tmp;
}

void Quicksort(int left, int right) {
	int i = left, j = right, pivot = V[(left + right) >> 1].cost;
	while (i <= j) {
		while (V[i].cost < pivot) i++;
		while (V[j].cost > pivot) j--;
		if (i <= j) {
			Swap(i, j);
			i++;
			j--;
		}
	}
	if (left < j) Quicksort(left, j);
	if (i < right) Quicksort(i, right);
}

int Find(int node) {
	while (node != Dad[node]) {
		node = Dad[node];
	}
	return node;
}

void Union(int x, int y) {
	if (Rank[x] > Rank[y]) {
		Dad[y] = x;
	}	else {
		Dad[x] = y;
	}
	if (Rank[x] == Rank[y]) Rank[y]++;
}

int Kruskal(int n, int m) {
	int i, min_cost = 0;
	Quicksort(0, m - 1);
	for (i = 1; i <= n; i++) {
		Dad[i] = i;
	}
	for (i = 0; i < m; i++) {
		int rx = Find(V[i].x);
		int ry = Find(V[i].y);
		if (rx != ry) {
			min_cost += V[i].cost;
			Apm[size].x = V[i].x;
			Apm[size++].y = V[i].y;
			Union(rx, ry);
		}
	}
	return min_cost;
}

int main() {
	FILE *fin = fopen("apm.in", "r");
	FILE *fout = fopen("apm.out", "w");
	int n, m, i;
	fscanf(fin, "%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		fscanf(fin, "%d %d %d", &V[i].x, &V[i].y, &V[i].cost);
	}
	int min_cost = Kruskal(n, m);
	fprintf(fout, "%d\n%d\n", min_cost, n - 1);
	for (i = 0; i < size; i++) {
		fprintf(fout, "%d %d \n", Apm[i].x, Apm[i].y);
	}
	fprintf(fout, "\n");
    return 0;
}