#include <stdio.h>
#include <algorithm>
using namespace std;
const int nmax=400001;
int n,m;
unsigned short t[nmax/2],h[nmax/2];
int nrm,smax;

struct muchie
{unsigned short int x,y;
 float c;};

muchie a[nmax],b[nmax];

void read()
{int i,x1,y1,z;
 scanf("%d%d",&n,&m);
 for(i=1;i<=m;++i)
   {scanf("%d%d%d",&x1,&y1,&z);
    a[i].x=x1; a[i].y=y1; a[i].c=z;
   }
}

int Find(int x)
{ while(t[x]!=0) x=t[x];
  return x;
}

void Union(int i, int j)
{if(h[i]>h[j]) t[j]=i;
 else
  {t[j]=i;
   if(h[j]==h[i]) h[j]++;
  }
}

void kruskal()
{int i;
 int x1,x2,v1,v2;
 for(i=1;i<=n;++i) h[i]=1;
 i=1;
 while(nrm<n-1)
 {v1=a[i].x; v2=a[i].y;
  x1=Find(v1); x2=Find(v2);
  if(x1!=x2)
    {nrm++;
     b[nrm].x=a[i].x;
     b[nrm].y=a[i].y;
     smax+=a[i].c;
     Union(x1,x2);}
  i++;
 }
}
inline bool comp(muchie e1, muchie e2)
{return e1.c<e2.c;}

int main()
{freopen("apm.in","r",stdin);
 freopen("apm.out","w",stdout);
 read();
 sort(a+1,a+m+1,comp);
 kruskal();
 printf("%d\n",smax);
 printf("%d\n",n-1);
 for(int i=1;i<=nrm;i++)
    {printf("%d ",b[i].x);
     printf("%d\n",b[i].y);
    }

 return 0;
}