#include<stdio.h>
#include<algorithm>
using namespace std;
int rad[200005],n,m,sol[200005],i,cost,nr;
struct str
{
  int x,y,c;
};
str v[400005];
bool sortare(str a , str b)
{
  return a.c<b.c;
}
int radacina(int nod)
{
  if(rad[nod]==nod)
    return nod;
  else
  {
    rad[nod]=radacina(rad[nod]);
    return rad[nod];
  }
}
int main()
{
  freopen("apm.in","r",stdin);
  freopen("apm.out","w",stdout);
  scanf("%d%d",&n,&m);
  for(i=1;i<=m;i++)
    scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
  sort(v+1,v+1+m,sortare);
  for(i=1;i<=n;i++)
    rad[i]=i;
  for(i=1;i<=m;i++)
  {
    rad[v[i].x]=radacina(v[i].x);
    rad[v[i].y]=radacina(v[i].y);
    if(rad[v[i].x]!=rad[v[i].y])
    {
      rad[v[i].y]=rad[v[i].x];
      cost+=v[i].c;
      nr++;
      sol[nr]=i;
    }

  //  return 0;
  }
  printf("%d\n%d\n",cost,n-1);
  for(i=1;i<=nr;i++)
      printf("%d %d\n",v[i].x,v[i].y);
  return 0;
}