#include      <iostream>
#include      <fstream>
#include      <queue>
#include      <vector>
#include      <algorithm>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

int n, m, k, tt[400005], rg[400005], total;
bool viz[400005];

pair < int, int > P[400005];

struct edge {
	int x, y, c;

}G[400005];

bool comp(edge a, edge b) {
	return a.c < b.c;
}

int Find(int nod) {
	while (tt[nod] != nod) {
		nod = tt[nod];
	}
	return nod;
}

void Unite(int x, int y) {
	if (rg[x] < rg[y]) {
		tt[x] = y;
	}
	if (rg[x] > rg[y]) {
		tt[y] = x;
	}
	if (rg[x] == rg[y]) {
		tt[x] = y;
		rg[y]++;
	}
}

int main() {

	ios::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);

	in >> n >> m;
	
	for (int i = 1; i <= m; i++)
		in >> G[i].x >> G[i].y >> G[i].c;

	sort(G + 1, G + m + 1, comp);

	for (int i = 1; i <= m; i++) tt[i] = i, rg[i] = i;

	for (int i = 1; i <= m; i++) {
		if (Find(G[i].x) != Find(G[i].y)) {
			Unite(Find(G[i].x), Find(G[i].y));
			P[++k].first = G[i].x;
			P[k].second = G[i].y;
			total += G[i].c;
		}
	}

	out << total << '\n';
	out << n - 1 << '\n';
	for (int i = 1; i < n; i++) {
		out << P[i].first << ' ' << P[i].second << '\n';
	}

	return 0;
}