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

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

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


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;

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