#include <stdio.h>
using namespace std;
#define MMAX 400006
#define NMAX 200006
int x[MMAX],y[MMAX],n,m;
int c[MMAX];
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 main()
{
 citire(); 
 int i,j;
 for (i=1;i<=n;++i) {g[i]=i; rang[i]=i;}
 for (i=1;i<m;++i) 
  for (j=i+1;j<=m;++j)
	if (c[i]>c[j]) {int 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;
	               }
 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;
}