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

int poz(int ls,int 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=ii;
	ii=-jj;
	jj=-aux;
	}
       ld+=ii;
       ls+=jj;
   }
    return ls;
}


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



int main()
{long i,co,nr,x,y;

 fin>>n>>m;

 for(i=1;i<=m;i++)
   {fin>>x>>y>>co;
      a[i].c1=x;
      a[i].c2=y;
      a[i].cost=co;
    }

  quick(1,m);
  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;
    }