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

int f(int x) {
	if (p[x] == x) return x;
	p[x] = f(p[x]);
	return p[x];
}

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

muchie sol[200000];

void kr() {
	int pos = 0;
	int cost = 0;
	for (int i = 0; i < m; i++) {
		if (p[muchii[i].p1] != p[muchii[i].p2]) {
			f(muchii[i].p1);
			un(muchii[i].p1, muchii[i].p2);
			muchii[pos].p1 = muchii[i].p1;
			muchii[pos].p2 = muchii[i].p2;
			cost += muchii[i].len;
			if (++pos == n - 1) break;
		}
	}
	cout << cost << "\n" << pos << "\n";
	for (int i = 0; i < pos; i++) {
		cout << muchii[i].p1 << " " << muchii[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();
}