#include <iostream>
#include <fstream>
#define NMAX 110
#define MAXEdges NMAX*(NMAX-1)/2

using namespace std;

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

struct Muchie {int e1, e2, cost;};
Muchie G[MAXEdges];
int A[NMAX], c[NMAX], n, m;

void init()
{
	f >> n >> m;
	for (int i = 1; i <= m; i++)
		f >> G[i].e1 >> G[i].e2 >> G[i].cost;
	for (int i = 1; i <= n; i++) c[i] = i;
	f.close();
}

void sortareMuchii(int st, int dr)
{
	int i, j;
	Muchie x;
	if (st < dr)
	{
		x = G[st]; i = st; j = dr;
		while (i < j)
		{
			while (i < j && G[j].cost >= x.cost)
				j--;
			G[i] = G[j];
			while (i < j && G[i].cost <= x.cost)
				i++;
			G[j] = G[i];
		}
		G[i] = x;
		sortareMuchii(st, i-1);
		sortareMuchii(i+1, dr);
	}
}

void afisare()
{
	int CostAPM = 0;
	for (int i = 1; i < n; i++)
		CostAPM += G[A[i]].cost;
	g << CostAPM << '\n' << n-1 << '\n';
	for (int i = 1; i < n; i++)
		g << G[A[i]].e1 << ' ' << G[A[i]].e2 << '\n';
	g.close();
}

int main()
{
	int i, j, Min, Max, NrMSel;
	init();
	sortareMuchii(1, m);
	NrMSel = 0;
	for (i = 1; NrMSel < n-1; i++)
		if (c[G[i].e1] != c[G[i].e2])
		{
			A[++NrMSel] = i;
			if (c[G[i].e1] < c[G[i].e2])
			{
				Min = c[G[i].e1];
				Max = c[G[i].e2];
			}
			else
			{
				Min = c[G[i].e2];
				Max = c[G[i].e1];
			}
			for (j = 1; j <= n; j++)
				if (c[j] == Max) c[j] = Min;
		}
	afisare();
	return 0;
}