#include <stdio.h>
#include <stdlib.h>

struct o_muchie
{
	int nod1, nod2, val, sel;
};

int n, m, cost_total = 0;
int *t, *h;
o_muchie *muchie;

void read();
void solve();
void write();
void unify(int, int);
int find(int);
int cmp(const void*, const void*);

int main()
{
	read();
	qsort (muchie + 1, m, sizeof (o_muchie), cmp);
	solve();
	write();
	return 0;
}

int find(int x)
{
	if (x == t[x])
	{
		return x;
	}
	t[x] = find(t[x]);
	return t[x];
}

void unify(int x, int y)
{
	if (h[x] > h[y])
	{
		t[y] = x;
	}
	else
	{
		t[x] = y;
		if (h[x] == h[y])
		{
			++h[y];
		}
	}
}

void solve()
{
	int i, x, y;
	for (i = 1; i <= m; ++i)
	{
		x = find(muchie[i].nod1);
		y = find(muchie[i].nod2);
		if (x != y)
		{
			unify(x, y);
			cost_total += muchie[i].val;
			muchie[i].sel = 1;
		}
	}
}

int cmp(const void *a, const void *b)
{
	o_muchie muc1 = *(o_muchie*)a, muc2 = *(o_muchie*)b;
	return muc1.val - muc2.val;
}

void write()
{
	int i;
	FILE *fout = fopen ("apm.out", "w");
	fprintf (fout, "%d\n%d\n", cost_total, n - 1);
	for (i = 1; i <= m; ++i)
	{
		if (muchie[i].sel)
		{
			fprintf (fout, "%d %d\n", muchie[i].nod1, muchie[i].nod2);
		}
	}
	fclose (fout);
}

void read()
{
	int i;
	FILE *fin = fopen ("apm.in", "r");
	fscanf (fin, "%d%d", &n, &m);
	muchie = new o_muchie[m+1];
	for (i = 1; i <= m; ++i)
	{
		fscanf (fin, "%d%d%d", &muchie[i].nod1, &muchie[i].nod2, &muchie[i].val);
		muchie[i].sel = 0;
	}
	t = new int[n+1];
	h = new int[n+1];
	for (i = 1; i <= n; ++i)
	{
		t[i] = i;
		h[i] = 0;
	}
	fclose (fin);
}