#include <fstream.h>
#define NMAX 200001
#define MMAX 400001
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,L[NMAX];
struct muchie{int x,y,c;};
muchie u[MMAX];
void init() {for (int i=1;i<=n;i++) L[i]=i;}
void citire()
{int i,x,y,c; f>>n>>m;
 for(i=1;i<=m;i++) {f>>x>>y>>c; u[i].x=x; u[i].y=y; u[i].c=c;}
 f.close();
}
void sortare()
{int i,j; muchie aux;
 for(i=1;i<m;i++)
  for(j=i+1; j<=m;j++)
  if(u[i].c>u[j].c) {aux=u[i]; u[i]=u[j]; u[j]=aux;}
}
int main()
{int i=1,j,k=0,x,y,ct=0;
 citire();
 sortare();
 init();
 while(k<n-1)
  {if (L[u[i].x]!=L[u[i].y])
    {k++; ct=ct+u[i].c;
     x=L[u[i].y];
     y=L[u[i].x];
     for (j=1;j<=n;j++) if(L[j]==x) L[j]=y;
    }
   i++;
  }
 g<<ct<<'\n'<<n-1<<'\n';
 for(i=1; i<n; i++)
  g<<u[i].x<<' '<<u[i].y<<'\n';
 g.close(); f.close();
 return 0;
}