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

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

nod *v[Nmax],*p;

int main()

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

f>>n>>m;

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


 {

   f>>x>>y>>z;

   p=new nod;

   p->inf=y;
   p->cost=z;
   p->adr=v[x];
   v[x]=p;

   p=new nod;

   p->inf=x;
   p->cost=z;
   p->adr=v[y];
   v[y]=p;
 }




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


poz=1;

while(poz)

{

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

   { if(l[p->inf])

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

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

   }

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

}

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

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

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


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

return 0;
}