#include <fstream.h>

#define inf 20105
#define max 2005

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




long a[max][max],v[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;
/////////////////// aici am modificat //////////////
/////////////////// in teste au pus muchii intre aceleasi 2 noduri dar cu cost diferite ///////
/////////////////// iar fara if ramane ultima citita //////////
  if(a[x][y]>c)
   a[x][y]=a[y][x]=c;
  }


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


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

 cost+=a[k][v[k]];
 v[k]=-v[k];

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


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

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

 fout.close();
 return 0;
 }