#include <stdio.h>
#define dim 400000

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

void qsort(int st, int dr)
{
	int i=st, j=dr, t, v=l[(st+dr)/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 find(int x)
{
	int r, y;
	for (r=x; r!=cc[r]; r=cc[r]);
	while (x!=cc[x])
	{
		y=cc[x];
		cc[x]=r;
		x=y;
	}
	return r;
}

void unite(int x, int y)
{
	if (gr[x]>gr[y]) cc[find(y)]=x;
	else cc[find(x)]=y;
	if (gr[x]==gr[y]) gr[x]++, gr[y]++;
}

void kruskal()
{
	int i, in;
	qsort(1, m);
	for (i=1; i<=n; i++) cc[i]=i, gr[i]=1;
	in=1;
	i=1;
	while (i<n)
	{
		if (find(l[in][0])!=find(l[in][1]))
		{
			cost+=l[in][2];
			vec[i][0]=l[in][0];
			vec[i][1]=l[in][1];
			unite(l[in][0], l[in][1]);
			i++;
		}
		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;
}