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

struct muchie
{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;
   }
 for(i=1;i<=n;i++) t[i]=i;
}

int Find(int x)
{ if(t[x]==x) return x;
  t[x]=Find(t[x]);
  return t[x];
}

void Union(int i, int j)
{i=Find(i);
 j=Find(j);
 if(i!=j) t[i]=j;
}

void kruskal()
{int i;
 for(i=1;i<=m;i++)
    if(Find(a[i].x)!=Find(a[i].y))
     {smax+=a[i].c;
      nrm++;
      b[nrm].x=a[i].x; b[nrm].y=a[i].y;
      Union(a[i].x,a[i].y);
     }
}

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;
}