#include<stdio.h>
using namespace std;

typedef struct
{
   long int x;
   long int y;
   int t;
   int c;
} muchie;

long int n;
long int m;
char viz[200001];
muchie A[400001];
FILE *f = fopen("apm.out","w");

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

void bubblesort(void)
{
     int gata = 1;
     muchie aux;
//     do
//     {
//        gata = 1;
        for(int j=1;j<m;j++)  
           for(int i=j+1;i<=m;i++)
              if(A[j].c>A[i].c)
              {
                aux = A[i];
                A[i] = A[j];
                A[j] = aux;
             //gata = 0;
              } 
//     }
//     while(!gata);
}

void parcurgere(void)
{
     int S = 0;
     int nr = 0;
//	 viz[A[1].x] = 1;
//	 viz[A[1].y] = 1;
	 int tip = 1;
     for(int i=1;i<=m && nr<n-1;i++)
     {
        if(viz[A[i].x] == 0 || viz[A[i].y] == 0)
        {
          A[i].t = 1;
          if(viz[A[i].x] == 0 && viz[A[i].y] == 0)
		  {
		  tip ++;
		  viz[A[i].x] = tip;
          viz[A[i].y] = tip;
          }
		  else
		  if(viz[A[i].x] == 0)
		    viz[A[i].x] = viz[A[i].y];
		  else
		  if(viz[A[i].y] == 0) 
			viz[A[i].y] = viz[A[i].x];
		  S += A[i].c;
          nr++;
        }
        else
          A[i].t = 0;
     }
     while(nr<n-1)
     {
       for(int i=1;i<=m && nr<n-1;i++)
          if(!A[i].t && viz[A[i].x] != viz[A[i].y])
          {
			for(int j=1;j<=m;j++)
				if(viz[j] == viz[A[i].x]) viz[j] = 1;
			    else if(viz[j] == viz[A[i].y]) viz[j] = 1;
            A[i].t = 1;
            nr++;
            S += A[i].c;
          }  
     }
     fprintf(f,"%d\n",S);
}

void afisare(void)
{
     fprintf(f,"%d\n",n-1);
     for(int i=1;i<=m;i++)
        if(A[i].t > 0)
          fprintf(f,"%d %d\n",A[i].y,A[i].x);
}

int main()
{
    citire();
    bubblesort();
    parcurgere();
    afisare();
    fclose(f);
	return 0;
}