#include<fstream.h>
#include<stdlib.h>
#define nmax 200004
#define nmax2 400005
int rg[nmax],fej[nmax],n,m,mukie[nmax];
struct szar
 {
  int e1,e2,cost;
 } ;
szar el[nmax2];

int cmp_s(const void *a,const void *b)
 { return (((szar*)a)->cost-((szar*)b)->cost); }

int go (int x)
 {
  int r,y;
  for (r=x;fej[r]!=r;r=fej[r])
     ;
  for ( ;fej[x]!=r; )
   {
    y=fej[x];
    fej[x]=r;
    x=y;
   }
  return r;
 }

void egyesit (int x,int y)
 {
  if (rg[x]>rg[y])
    fej[y]=x;
  else
    fej[x]=y;
  if (rg[x]==rg[y])
    rg[y]++;
 }

int main()
 {
  ifstream be("apm.in");
  be>>n>>m;
  int i;
  for (i=1;i<=m;++i)
   { be>>el[i].e1;
     be>>el[i].e2;
     be>>el[i].cost;
   }
  for (i=1;i<=n;++i)
   {
    fej[i]=i;
    rg[i]=1;
   }
  el[0].cost=-1500;
  qsort(el,m+1,sizeof(szar),cmp_s);
  int nr=0,sz=0,r1,r2;
  for (i=1;nr<n-1;++i)
   {
    r1=go(el[i].e1);
    r2=go(el[i].e2);
    if (r1!=r2)
     {
      sz+=el[i].cost;
      mukie[++nr]=i;
      egyesit(r1,r2);
     }
   }
  ofstream ki ("apm.out");
  ki<<sz<<'\n'<<nr<<'\n';
  for (i=1;i<=nr;++i)
    ki<<el[mukie[i]].e1<<" "<<el[mukie[i]].e2<<'\n';
  ki.close();
  return 0;
 }