#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAX_N 200001


int Arbore[2 * MAX_N];
int x[2 * MAX_N], y[2 * MAX_N], cost[2 * MAX_N];
int R[MAX_N], indici[MAX_N];
int cost_apm;
int n, m, muchii = 0;

int comp_conexa(int a)
{
	if (R[a] == a)
		return a;
	R[a] = comp_conexa(R[a]);
	return R[a];
}

void join(int a, int b)
{
	R[comp_conexa(a)] = comp_conexa(b);
}

bool cmp(int x, int y)
{
	return (cost[x] < cost[y]);
}

int main()
{
	std::ifstream f("apm.in");
	f >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		f >> x[i] >> y[i] >> cost[i];
		indici[i] = i;
		R[i] = i;
	}
	std::sort(indici + 1, indici + m + 1, cmp);
	for (int i = 1; i <= m; i++)
	{
		if (comp_conexa(x[indici[i]]) != comp_conexa(y[indici[i]]))
		{
			cost_apm += cost[indici[i]];
			join(x[indici[i]], y[indici[i]]);
			Arbore[++muchii] = indici[i];
		}
	}
	std::ofstream g("apm.out");
	g << cost_apm << "\n" << n-1 <<"\n";
	for (int i = 1; i <= muchii; i++)
		g << x[Arbore[i]] << " " << y[Arbore[i]] << "\n";
	return 0;
}