#include<fstream.h>
ifstream fin("apm.in");
ofstream fout("apm.out");
#define max 200000
struct muchie {long c1,c2,cost;};
muchie a[max],b[max];
char viz[max];
long n,m,nr;
long c;

long poz(long ls,long ld)
{ int ii=0,jj=-1,aux;
muchie d;

while(ls<ld)
  {if(a[ls].cost>a[ld].cost)
       {d=a[ld];
        a[ld]=a[ls];
        a[ls]=d;
        aux=-jj;
        jj=-ii;
        ii=aux;
        }
       ld+=ii;
       ls+=jj;
   }
    return ld;
}


void quick(long ld,long ls)
{long k;
if(ld<ls)
  {k=poz(ld,ls);
   quick(ld,k-1);
   quick(k+1,ls);
   }
}


int main()
{long i,co,nr,x,y;
  nr=0;
 fin>>n>>m;
 for(i=1;i<=m;i++)
   {fin>>x>>y>>co;
      nr++;
      a[nr].c1=x;
      a[nr].c2=y;
      a[nr].cost=co;
    }

  quick(1,nr);
  viz[a[1].c1]=1;
  viz[a[1].c2]=1;

  b[1]=a[1];
  c=a[1].cost;

  long j;

  for(i=2;i<n;i++)
   {for(j=1;viz[a[j].c1]==viz[a[j].c2];j++);
         viz[a[j].c1]=1;
         viz[a[j].c2]=1;
         c+=a[j].cost;
         b[i]=a[j];
     }

    fout<<c<<'\n'<<(n-1)<<'\n';

     for(i=1;i<n;i++)
      fout<<b[i].c1<<" "<<b[i].c2<<'\n';

    fin.close();
    fout.close();
    return 0;
    }