# include <iostream.h>
# include <fstream.h>

fstream f("apm.in",ios::in);
fstream g("apm.out",ios::out);

int n,m,l[800];

struct muchie
{
	int x,y,c;
}v[800];

struct muchii
{
	int x,y;
}w[800];

void init()
{
	int i=0;
	for(i=1;i<=n;i++) l[i]=i;
}

void citire()
{
	int i=0,x,y,c;f>>n>>m;
	while(f>>x>>y>>c)
	{
		i++;
		v[i].x=x;v[i].y=y;
		v[i].c=c;
	}
	f.close();m=i;
}

void sortare()
{
	int i,j;muchie aux;
	for(i=1;i<m;i++)
		for (j=i+1;j<=m;j++)
			if (v[i].c>v[j].c)
			{
				aux=v[i];v[i]=v[j];v[j]=aux;
			}
}

int main()
{
	int i=1,j,k=0,x,y,ct=0;
	citire();
	sortare();
	init();
	while(k<n-1)
	{
		if(l[v[i].x]!=l[v[i].y])
		{
			k++;ct=ct+v[i].c;
			
			w[i].x=v[i].x; w[i].y=v[i].y;
		
			x=l[v[i].y];
			y=l[v[i].x];
			for(j=1;j<=n;j++)
				if(l[j]==x) l[j]=y;
		}
		i++;
	}
	g<<ct<<"\n"<<k<<"\n";
	for(i=1;i<=n-1;i++) 
		g<<w[i].y<<" "<<w[i].x<<"\n";
	
	
	return 0;
}