#include <stdio.h>
using namespace std;
#define MMAX 400006
#define NMAX 200006
int x[MMAX],y[MMAX],n,m;
int c[MMAX],aux;
int g[NMAX],rang[NMAX];
const int CST=1007;

void citire()
{
 FILE *fin=fopen("apm.in","r");
 fscanf(fin,"%d%d",&n,&m);
 for (int i=1;i<=m;++i)
  fscanf(fin,"%d%d%d",&x[i],&y[i],&c[i]);
 fclose(fin);
}

int radacina(int a)
{
 int r=a,aux;
 while (r!=g[r]) { r=g[r];}
 while (g[a]!=a)
  { aux=g[a]; g[a]=r; a=aux;}
 return r;
}

void unite(int a, int b)
{
 if (rang[a]<rang[b]) g[b]=g[a];
    else g[a]=g[b];
 if (rang[a]==rang[b]) rang[a]++;
}

int poz(int i, int j)
{ int di=1,dj=0;
  while (i<j)
   {
	if (c[i]>c[j]) {
		            aux=c[i];c[i]=c[j];c[j]=aux;
					aux=x[i];x[i]=x[j];x[j]=aux;	
					aux=y[i];y[i]=y[j];y[j]=aux;
					i^=di; j^=dj;
	               }
	i+=di; j-=dj;
   }
  return i;
}
void qsort(int st, int dr)
{
 if (st<dr) {int p = poz(st,dr); qsort(st,p-1); qsort(p+1,dr);}
}

int main()
{
 citire(); 
 int i;
 for (i=1;i<=n;++i) {g[i]=i; rang[i]=i;}
 qsort(1,m);
 int nm=0; long Cost=0;
 for (i=1;i<=m;++i)	
  {   int rx,ry;
	 rx=radacina(x[i]); ry=radacina(y[i]);
	 if (rx!=ry)
      {
		Cost+=c[i]; nm++;
		unite(rx,ry);
      }
	  else c[i]=CST; //nu a fost selectata
  }	
 FILE *fout=fopen("apm.out","w");
 fprintf(fout,"%ld\n",Cost); 
 fprintf(fout,"%d\n",nm);
 for (i=1;i<=m;++i)
  if (c[i]!=CST) fprintf(fout,"%d %d\n",x[i],y[i]);
 return 0;
}