#include <cstdio>
#include <algorithm>
#define NMAX 200001
#define MMAX 400001
using namespace std;
FILE *fin=fopen("apm.in", "r");
FILE *fout=fopen("apm.out", "w");

struct lista_muchii
{
	int x, y, cost;
} lm[MMAX];

int n, m, cmin, sel[MMAX], cc[NMAX], nsel;

void citire();
void rulare();
void afisare();
bool crit(lista_muchii a, lista_muchii b)
{
	return a.cost<=b.cost;
}
bool mergePus(int a);

int main()
{
	citire();
	rulare();
	afisare();
	return 0;
}

void citire()
{
	int i;
	fscanf(fin, "%d %d", &n, &m);
	for (i=1; i<=m; i++) fscanf(fin, "%d %d %d", &lm[i].x, &lm[i].y, &lm[i].cost);
}

void afisare()
{
	int i;
	fprintf(fout, "%d\n%d\n", cmin, n-1);
	for (i=1; i<=n-1; i++) fprintf(fout, "%d %d\n", lm[sel[i]].x, lm[sel[i]].y);
}

void rulare()
{
	int i, t, k;
	sort (lm+1, lm+m+1, crit);
	for (i=1; i<=n; i++) cc[i]=i;
	i=1;
	while (nsel<n-1)
	{
		if (mergePus(i))
		{
			nsel++;
			sel[nsel]=i;
			cmin+=lm[i].cost;
			k=cc[lm[i].y];
			for (t=1; t<=n; t++) if (cc[t]==k) cc[t]=cc[lm[i].x];
		}
		i++;
	}
}

bool mergePus(int a)
{
	return cc[lm[a].x]!=cc[lm[a].y];
}