#include<stdio.h>
using namespace std;

FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");

#define M 400010
long n,m;
long a[M/2],c[M/2];

typedef struct
{
	long x,y;
	int c;
}VF;
VF v[M];

void cit()
{
	long i;
	fscanf(f,"%ld%ld",&n,&m);
	for(i=1;i<=m;++i)
		fscanf(f,"%ld%ld%d",&v[i].x,&v[i].y,&v[i].c);
	fclose(f);
	for(i=1;i<=n;++i)
		c[i]=i;
}

void afis()
{
	int i,cost=0;
	for(i=1;i<n;++i)
		cost+=v[a[i]].c;
	fprintf(g,"%ld\n%ld\n",cost,n-1);
	for(i=1;i<n;++i)
		fprintf(g,"%ld %ld\n",v[a[i]].x,v[a[i]].y);
}

void sort(long st, long dr)
{
	long i,j;
	VF x;
	if(st<dr) {x=v[st];
			   i=st;
			   j=dr;
			   while(i<j)
			   {
				   while(i<j && v[j].c>=x.c) j--;
				   v[i]=v[j];
				   while(i<j && v[i].c<=x.c) i++;
				   v[j]=v[i];
			   }
			   v[i]=x;
			   sort(st,i-1);
			   sort(i+1,dr);
				}
}

int main()
{
	cit();
	sort(1,m);
	
	long i,j,min,max,nr;
	nr=0;
	for(i=1;nr<n-1;i++)
		if(c[v[i].x]!=c[v[i].y]) {a[++nr]=i;
								  if(c[v[i].x]<c[v[i].y]) {min=c[v[i].x]; max=c[v[i].y];}
								  else {min=c[v[i].y]; max=c[v[i].x];}
								  
								  for(j=1;j<=n;++j)
									  if(c[j]==max) c[j]=min;
									}
	afis();
	return 0;
}