# include <fstream.h>
ifstream f ("apm.in");
ofstream g ("apm.out");
int sol[200005],h[200005],poz[200005],min2,aux,i,min,m,costf,x,y,z,k,n,c[200005],inf=1000000,q[200005];

  struct nod 
  {
	  int info,cost;
	  nod *urm;
  }
*a[100],*p,*v;

 
  void sss (int i)
  {
	  if (i/2>=1)
	  if (c[h[i/2]]>c[h[i]])
	  {
		  aux=h[i];
		  h[i]=h[i/2];
		  h[i/2]=aux;
	      poz[h[i]]==i;
		  poz[h[i/2]]=i/2;
	       sss (i/2);  
	  }
  }

void jjj (int i)
{
	
	if (m>=2*i+1)
	{
	 if (c[h[2*i]]>c[h[2*i+1]])
		min2=2*i+1;
	 else
		min2=2*i;
	}
	else
		if (m==2*i)
			min2=2*i;
	if (m>=2*i)
	 if (c[h[min2]]<c[h[i]])
	 {
		aux=h[i];
		h[i]=h[min2];
		h[min2]=aux;
		poz[h[i]]=i;
		poz[h[min2]]=min2;
	 jjj (min2);
	 }
	
}

 void adauga (int x)
  {
	  m++;
	  h[m]=x;
	  poz[x]=m;
	  sss (m);
 }

 void sterg ()
 {
	 poz[h[1]]=inf;
	 h[1]=h[m];
	 m--;
	 jjj (1);
 }

int main ()
{
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		f>>x>>y>>z;
		
	p=new nod;
	p->info=y;
	p->cost=z;
	p->urm=a[x];
	a[x]=p;
	p=new nod;
	p->info=x;
	p->cost=z;
	p->urm=a[y];
	a[y]=p;
	
	}
	
	h[1]=1;
	m=1;
	poz[1]=1;
	for (i=1;i<=n;i++)
	{
		
		min=h[1];
		sterg();
		costf=costf+c[min];
		k++;
		sol[k]=min;
		p=a[min];
		while (p)
		{
			if (poz[p->info]==0)
				{
					c[p->info]=p->cost;
					q[p->info]=min;
					adauga (p->info);
				}
			  else
				  if (c[p->info]>p->cost && poz[p->info]!=inf)
					  {
						  c[p->info]=p->cost;
						  q[p->info]=min;
						  sss (poz[p->info]);
					  }
		p=p->urm;
		}
          	
	}
	
	g<<costf<<"\n";
	g<<n-1<<"\n";
	for (i=2;i<=k;i++)
		g<<sol[i]<<" "<<q[sol[i]]<<"\n";
	return 0;
}