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

int n,nrm,k=1,mu,s=0;
int t[50],h[50],m[3][50],a[2][50];


void citire()
{
	ifstream f("apm.in");
	f>>n>>mu;
	for(int i=1;i<=mu;i++)
		f>>m[0][i]>>m[1][i]>>m[2][i];
	f.close();
}


void sortare()
{
	int aux,ok;
	do
	{
	ok=0;
	for(int i=1;i<mu;i++)
		if(m[2][i]>m[2][i+1])
			{
			aux=m[0][i];
			m[0][i]=m[0][i+1];
			m[0][i+1]=aux;

			aux=m[1][i];
			m[1][i]=m[1][i+1];
			m[1][i+1]=aux;

			aux=m[2][i];
			m[2][i]=m[2][i+1];
			m[2][i+1]=aux;

			ok=1;
			}
	}while(ok);

}


int arb(int nod)
	{
	while(t[nod])
		nod=t[nod];
	return nod;
	}


int main()
{
	ofstream f("apm.out");
	citire();
	
	sortare();

	k=1;
	do
	{
	while(arb(m[0][k])==arb(m[1][k]))
		k++;
	nrm++;
	s=s+m[2][k];
	a[0][k]=m[0][k];
	a[1][k]=m[1][k];
	if(h[m[0][k]]==h[m[1][k]])
		{
		t[m[0][k]]=m[1][k];
		h[m[1][k]]++;
		}
	else
		if(h[m[0][k]]<h[m[1][k]])
			t[m[0][k]]=m[1][k];
		else
			t[m[1][k]]=m[0][k];
	k++;
	}while(nrm<n-1);
	
	f<<s<<"\n"<<nrm<<"\n";
	for(int i=1;i<=nrm;i++)
		f<<a[0][i]<<" "<<a[1][i]<<"\n";
	return 0;
}