#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define dim 400000

int n, m, l[dim+1][3]={0}, cost=0, vec[dim/2+1][2], cc[dim/2+1];

void qsort(int st, int dr)
{
	srand((unsigned)time(NULL));
	int i=st, j=dr, t, v=l[(dr+st)/2][2];
	do
	{
		while (l[i][2]<v) i++;
		while (l[j][2]>v) j--;
		if (i<=j)
		{
			t=l[i][0], l[i][0]=l[j][0], l[j][0]=t;
			t=l[i][1], l[i][1]=l[j][1], l[j][1]=t;
			t=l[i][2], l[i][2]=l[j][2], l[j][2]=t;
			i++, j--;
		}
	} while (i<=j);
	if (st<j) qsort(st, j);
	if (i<dr) qsort(i, dr);
}

int grupa(int i)
{
	if (cc[i]==i) return i;
	cc[i]=grupa(cc[i]);
	return cc[i];
}

void mod(int x, int v)
{
	cc[grupa(x)]=grupa(v);
}

void kruskal()
{
	int i, in;
	qsort(1, m);
	for (i=1; i<=n; i++) cc[i]=i;
	in=1;
	for (i=1; i<=m; i++)
	{
		if (grupa(l[i][0])!=grupa(l[i][1])) 
		{
			cost+=l[i][2];
			vec[in][0]=l[i][0];
			vec[in][1]=l[i][1];
			mod(l[i][0], l[i][1]);
			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][0], &l[i][1], &l[i][2]);
	kruskal();
	printf("%d\n%d\n", cost, n-1);
	for (i=1; i<=n-1; i++)
		printf("%d %d\n", vec[i][0], vec[i][1]);
	return 0;
}