#include <fstream>
#define InFile "apm.in"
#define OutFile "apm.out"
#define NMAX 100
#define MMAX 1000
using namespace std;

ofstream fout(OutFile);
int C[NMAX],n,m,much,cost;
struct arc{int x,y,c;} M[MMAX],aux,B[NMAX];
void citire();
void kruskal();
void afisare();
int Divide (int st, int dr) 
	{
	int i=st, j=dr, di=0, dj=1;
	while(i < j)
	{ 
		if(M[i].c > M[j].c)
		{ 
			aux=M[i];
			M[i]=M[j];
			M[j]=aux;
			di=1-di;
			dj=1-dj; 
		}
		i+=di;
		j-=dj; 
	}
	return i;
	}
void QSort(int st, int dr)
{
	int poz;
	if (st<dr) 
		{
			poz=Divide(st,dr);
			QSort(st,poz-1);
			QSort(poz+1,dr);
		}
}
int main()
{
	citire();
	QSort(0,m-1);
	kruskal();
	afisare();
	return 0;
}

void citire()
{
	ifstream fin(InFile);
	fin>>n>>m;
	for (int i=0;i<m;i++)
		fin>>M[i].x>>M[i].y>>M[i].c;
	for (int i=1;i<=n;i++)
		C[i]=i;
}

void kruskal()
{
	int aux;
	while (much<n-1)
	{
	for (int i=0;i<m;i++)
		{
		if (C[M[i].x]!=C[M[i].y])
			{
				aux=C[M[i].x];
				cost+=M[i].c;
				//fout<<M[i].x<<" "<<M[i].y<<"\n";
				B[much]=M[i];
				for (int k=1;k<=n;k++)
					if (C[k]==aux)
						C[k]=C[M[i].y];
				//C[M[i].x]=C[M[i].y]; reunim multimile 
				much++;
			}
		}
	}
}

void afisare()
{
	fout<<cost<<'\n'<<n-1<<"\n";
	for (int i=0;i<n-1;i++)
		{
			fout<<B[i].x<<" "<<B[i].y<<"\n";
		}
}