#include<cstdio>
#include<cstdlib>
#include<algorithm>

struct muchie
{ int x,y,c; };
muchie a[400001];

int n,m,t[100001],S,b[100001],c[100001],i;

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

void connect(int x,int y)
{
	x = T(x), y = T(y);
	if(x==y) return;
	if(rand()%2)
		t[x] = y;
	else
		t[y] = x;
}

bool connected(int x,int y)
{
	return T(x)==T(y);
}

int cmp(const void* a,const void* b)
{
	muchie A = *(muchie*)a, B = *(muchie*)b;
	if(A.c > B.c)
		return 1;
	if(A.c == B.c)
		return 0;
	return -1;
}

void kruskal()
{
	for(i=1;i<=n;++i)
		t[i] = i;
	qsort(&a[1],m,sizeof(muchie),cmp);
	int w = 1,i=1;
	while(w<n)
	{
		if(!connected(a[i].x,a[i].y))
		{
			connect(a[i].x,a[i].y);
			S+=a[i].c;
			b[w] = a[i].x;
			c[w] = a[i].y;
			++w;
		}
		++i;
	}
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;++i)
		scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
	kruskal();
	printf("%d\n%d\n",S,n-1);
	for(i=1;i<n;++i)
		printf("%d %d\n",b[i],c[i]);
	fclose(stdout);
	return 0;
}