#include<stdio.h>
#include<algorithm>
using namespace std;
#define nrd 200001
FILE *in=fopen("apm.in","r"),*out=fopen("apm.out","w");
typedef struct muchie{int x,y,c;};
muchie L[nrd];
int tata[nrd],cap[nrd],rez[nrd],n,m;
int ctat(int x)
{
	int aux;
	aux=x;
	while(tata[x]!=x)
		x=tata[x];
	tata[aux]=x;
	return x;
}
void unire(int x,int y)
{
	x=ctat(x);
	y=ctat(y);
	if(cap[x]>cap[y])
	{
		tata[y]=x;
		cap[x]+=cap[y];
	}
	else{ tata[x]=y; cap[y]+=cap[x];}
}
int cmp(muchie a,muchie b)
{
	return a.c<b.c;
}
int main()
{
	int i,k=0,S=0;
	fscanf(in,"%d %d",&n,&m);
	for(i=1;i<=n;i++)
	{
		tata[i]=i;
		cap[i]=1;
	}
	for(i=1;i<=m;i++)
		fscanf(in,"%d %d %d",&L[i].x,&L[i].y,&L[i].c);
	sort(L+1,L+m+1,cmp);
	for(i=1;i<=m;i++)
	{
		if(ctat(L[i].x)!=ctat(L[i].y))
		{
			unire(L[i].x,L[i].y);
			S+=L[i].c;
			rez[++k]=i;
		}
	}
	fprintf(out,"%d\n%d\n",S,n-1);
	for(i=1;i<n;i++)
		fprintf(out,"%d %d\n",L[rez[i]].x,L[rez[i]].y);
	return 0;
}