#include <stdio.h>
#define dim 400000

struct muc
{
	int st, dr, c;
};

muc l[dim+1], v[dim/2+1];
int n, m, cc[dim/2+1], cost=0;

void qsort(int st, int dr)
{
	int i=st, j=dr, t, v=l[(st+dr)/2].c;
	do
	{
		while (l[i].c<v) i++;
		while (l[j].c>v) j--;
		if (i<=j)
		{
			t=l[i].st, l[i].st=l[j].st, l[j].st=t;
			t=l[i].dr, l[i].dr=l[j].dr, l[j].dr=t;
			t=l[i].c, l[i].c=l[j].c, l[j].c=t;
			i++, j--;
		}
	} while (i<=j);
	if (st<j) qsort(st, j);
	if (i<dr) qsort(i, dr);
}

void mod(int x, int v)
{
	int i;
	for (i=1; i<=n; i++)
		if (cc[i]==x) cc[i]=v;
}

void kruskal()
{
	int i, in;
	qsort(1, m);
	for (i=1; i<=n; i++) cc[i]=i;
	in=1;
	for (i=1; i<=n-1; i++)
	{
		while (cc[l[in].st]==cc[l[in].dr]) in++;
		cost+=l[in].c;
		v[i]=l[in];
		if (cc[l[in].st]<cc[l[in].dr]) mod(cc[l[in].dr], cc[l[in].st]);
		else mod(cc[l[in].st], cc[l[in].dr]);
		in++;
	}
}

int main()
{
	int i;
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d %d\n", &n, &m);
	for (i=1; i<=m; i++) scanf("%d %d %d\n", &l[i].st, &l[i].dr, &l[i].c);
	kruskal();
	printf("%d\n%d\n", cost, n-1);
	for (i=1; i<=n-1; i++)
		printf("%d %d\n", v[i].st, v[i].dr);
	return 0;
}