#include<fstream.h>
#define INF 1<<7
#define Nmax 200010
int x,y,z,i,Cost,l[Nmax],c[Nmax],t[Nmax],n,m;

struct nod { int inf,cost; nod *adr;};

nod *v[Nmax];

int cauta_nod();

void add( int i, int j, int x)

 { nod *p;

   p=new nod;

   p->inf=j;
   p->cost=x;
   p->adr=v[i];
   v[i]=p;
 }
void apm (int x)

 {
   if(x){

    nod *p; int next;


  for(p=v[x];p;p=p->adr)

   { if(l[p->inf])

	  if(c[p->inf]>p->cost)

	    { c[p->inf]=p->cost;
		 l[p->inf]=x;
	    }

   }


    next=cauta_nod();
    apm(next);
  }

 }
int cauta_nod()

 { int minim=INF,poz=0;


   for(i=2;i<=n;i++)


  if(l[i]&&c[i]<minim) {minim=c[i]; poz=i;}


  t[poz]=l[poz]; l[poz]=0; Cost+=c[poz];

   return poz;

 }

int main()

{
ifstream f("apm.in");
ofstream g("apm.out");

f>>n>>m;

for(i=1;i<=m;i++)


 {

   f>>x>>y>>z;

   add(x,y,z);
   add(y,x,z);

 }




for(i=2;i<=n;i++) {l[i]=1; c[i]=INF;}


apm(1);

g<<Cost<<'\n'<<n-1<<'\n';

for(i=2;i<=n;i++)

 g<<i<<" "<<t[i]<<'\n';


f.close();
g.close();

return 0;
}