#include<iostream>
#include<fstream>

using namespace std;

long n,m;
long a[6000][6000];
long p[6000];
int viz[6000];//ii 0, nevizitat
int cmin[6000];
long prim;
long costt;

void citire()
{
	ifstream f("apm.in");
	long i,j,k;
	f>>n>>m;
	for(i=1;i<=n;i++) a[i][i]=0;
	for(i=1;i<=n;i++)	//infinit
		for(j=1;j<=n;j++)
			a[i][j]=1001;
		
	for(k=1;k<=m;k++) 
		{
			int c;
			f>>i>>j>>c;
			a[i][j]=c;
			a[j][i]=c;
		}
	f.close();
	// + intializare
	prim=1; //nimereala
	viz[prim]=1;
	for(i=1;i<=n;i++) 
		{
			p[i]=prim;
			cmin[i]=a[prim][i];
		}
		 
	f.close();
	
}

void afisare()
{
	ofstream g("apm.out");
	g<<costt<<endl<<n-1<<endl;
	for(long i=2;i<=n;i++) //ca am luat prim = 1;
		g<<i<<" "<<p[i]<<"\n";
	g.close();
}

int main()
{
citire();

			
long vfmin;
long nrv=0;
long i;
while(nrv<n-1)
{
	int cost=1001;
	for(i=1;i<=n;i++)
		if(!viz[i] && cmin[i]<cost) // nui vizitat si..
			{
				cost=cmin[i];
				vfmin=i;
			}
	viz[vfmin]=1; //l-am vizitat
	nrv++;
	costt+=cost;
	for(i=1;i<=n;i++)
		if(!viz[i] && a[vfmin][i]<cmin[i])
			{p[i]=vfmin;
			cmin[i]=a[vfmin][i];}
	
}
afisare();
return 0;
}