#include<fstream.h>
#include<stdlib.h>
#define nmax 200005
#define mmax 400005
int fej[nmax],rg[nmax];
struct asd
 {
  int e1,e2,cost;
 };
int mukie[nmax],n,m,nr;
asd a[mmax];
int cmp (const void *a,const void *b)
 {
  return (((asd*)a)->cost - ((asd*)b)->cost);
 }
int go (int x)
 {
  for (int r=fej[x];fej[r]!=r;r=fej[r]) ;
  int y;
  for (;fej[x]!=r;)
   {
    y=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");
  ofstream ki ("apm.out");
  be>>n>>m;
  int i,x,y,sz=0,r1,r2;
  for (i=1;i<=n;++i)
    {
     fej[i]=i;
     rg[i]=1;
    }
  for (i=1;i<=m;++i)
   {
    be>>a[i].e1>>a[i].e2>>a[i].cost;
   }
  be.close();
  a[0].cost=-1500;
  qsort(a,m+1,sizeof(asd),cmp);
  for (i=1;nr<n-1;++i)
   {
    r1=go(a[i].e1);
    r2=go(a[i].e2);
    if (r1!=r2)
     {
      sz+=a[i].cost;
      mukie[++nr]=i;
      egyesit(r1,r2);
     }
   }
  ki<<sz<<'\n'<<nr<<'\n';
  for (i=1;i<=nr;++i,ki<<'\n')
    ki<<a[mukie[i]].e1<<' '<<a[mukie[i]].e2;
  ki.close();
  return 0;
 }