#include<stdio.h>
#define dim 20000
#define inf 1005
using namespace std;

int n,m,nrv,i,j,mat[dim][dim],n1,n2,cost,r,cmin[dim],p[dim],vfmin;
short int z[dim];

int main()
{
 FILE *f=fopen("apm.in","r"), *g=fopen("apm.out","w");
 
 fscanf(f,"%d%d",&n,&m); nrv=n; //nrv=nr varfuri de selectat
 
 for(i=1;i<=n;i++)
 {
   for(j=1;j<=n;j++)
	mat[i][j]=inf;
 mat[i][i]=0;
 }
 
  for(i=1;i<=m;i++)
   {fscanf(f,"%d%d%d",&n1,&n2,&cost);
	mat[n1][n2]=cost; mat[n2][n1]=cost;
   }
   
  
r=1; //nod de start

 for(i=1;i<=n;i++)
 {cmin[i]=mat[r][i];
  p[i]=r;
  z[i]=1;
 }
 p[r]=0; z[r]=0; nrv--;
 
 
 while(nrv) //cat timp mai am varfuri de selectat
{
 cost=inf; //initializez costul la infinit, urmeaza sa calculez costul minim
 
  for(i=1;i<=n;i++)
  if(z[i] && cmin[i]<cost)
 {vfmin=i;
  cost=cmin[i];
 }
 
 z[vfmin]=0; //selectez varf
 nrv--;
 
 for(i=1;i<=n;i++)
if(z[i] && mat[i][vfmin]<cmin[i]) //caut muchie noua, cu cost mai mic
{cmin[i]=mat[i][vfmin];
 p[i]=vfmin;}
 
 }
cost=0; 
 for(i=1;i<=n;i++) cost+=cmin[i];
 
fprintf(g,"%d\n",cost);
fprintf(g,"%d\n",n-1);

for(i=1;i<=n;i++)
 if(i!=r) fprintf(g,"%d %d\n", i, p[i]);

fclose(f);
fclose(g);
return 0;
}