#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
#define cin fin
#define cout fout

typedef struct {
	int p1, p2, len;
} muchie;

int n, m;
muchie muchii[400001];
int p[200001];

bool compareMuchie(muchie m1, muchie m2) {
	return m1.len < m2.len;
}

void un(int x, int y) {
	for (int i = 1; i <= n; i++) {
		if (p[i] == x) {
			p[i] = p[y];
		}
	}
}

int sol[200000];

int min(int x, int y) {
	if (x < y) return x;
	return y;
}

int max(int x, int y) {
	if (x > y) return x;
	return y;
}

void kr() {
	int pos = 0;
	int cost = 0;
	for (int i = 0; i < m; i++) {
		if (p[muchii[i].p1] != p[muchii[i].p2]) {
			un(max(p[muchii[i].p1], p[muchii[i].p2]), min(p[muchii[i].p1], p[muchii[i].p2]));
			sol[pos] = i;
			cost += muchii[i].len;
			if (++pos == n - 1) break;
		}
	}
	cout << cost << "\n" << pos << "\n";
	for (int i = 0; i < pos; i++) {
		cout << muchii[sol[i]].p1 << " " << muchii[sol[i]].p2 << "\n";
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> muchii[i].p1 >> muchii[i].p2 >> muchii[i].len;
	}

	sort(muchii, muchii + m, compareMuchie);

	for (int i = 1; i <= n; i++) {
		p[i] = i;
	}
	kr();
}