#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <vector>

using namespace std;

struct graf{
	int a, b, cost;
} G[400005];
int compConexa[200005], A[200005];
int n, m, costAPM;

void citireMuchii();
void afisareAPM();
bool acomp(graf st, graf dr) { return st.cost < dr.cost; };

int main() {
	int i, nrMuchiiSel,max,min,j;

	citireMuchii();
	sort(G, G + m, acomp);

	nrMuchiiSel = 0;
	i = 0;
	while (nrMuchiiSel < n - 1) {
		if (compConexa[G[i].a] != compConexa[G[i].b]) {
			costAPM += G[i].cost;
			A[++nrMuchiiSel] = i;

			if (compConexa[G[i].a] > compConexa[G[i].b]) {
				min = compConexa[G[i].b];
				max = compConexa[G[i].a];
			}
			else {
				max = compConexa[G[i].b];
				min = compConexa[G[i].a];
			}

			for (j = 1; j <= n; j++)
				if (compConexa[j] == max)
					compConexa[j] = min;
		}

		i++;
	}

	afisareAPM();

	return 0;
}

void afisareAPM() {
	int i;

	ofstream fout("apm.out");

	fout << costAPM << '\n' << n - 1 << '\n';

	for (i = 1; i < n; ++i)
		fout << G[A[i]].a << ' ' << G[A[i]].b <<'\n';

	fout.close();
}

void citireMuchii() {
	int i;

	ifstream fin("apm.in");

	fin >> n >> m;
	for (i = 0; i < m; ++i)
		fin >> G[i].a >> G[i].b >> G[i].cost;

	for (i = 1; i <= n; i++)
		compConexa[i] = i;

	fin.close();
}