#include <fstream.h>

#define inf 2000;
#define max 20005

ifstream fin("apm.in");
ofstream fout("apm.out");




int a[max][max],v[max],t[max],k,n,m;
long cost;



int main()
{int i,j,x,y,c,min;

fin>>n>>m;


 for (i=1;i<=n;i++)
  for (j=i+1;j<=n;j++)
    a[j][i]=a[i][j]=inf;

for (i=1;i<=m;i++)
 {fin>>x>>y>>c;
  a[x][y]=a[y][x]=c;
  }


for (i=2;i<=n;i++)
 v[i]=t[i]=1;

v[1]=t[1]=0;

for (j=1;j<n;j++)
{min=inf;
  for (i=1;i<=n;i++)
    if (v[i] && min>a[i][v[i]])
     {k=i;
      min=a[i][v[i]];
     }

 t[k]=v[k];
 cost+=a[k][t[k]];
 v[k]=0;

 for (i=1;i<=n;i++)
  if (v[i] && a[i][v[i]]>a[i][k])
   v[i]=k;
}


fout<<cost<<'\n'<<n-1<<'\n';

for (i=2;i<=n;i++)
 fout<<t[i]<<" "<<i<<'\n';

 fout.close();
 return 0;
 }