#include<iostream>
using namespace std;

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

long int n;
long int m;
int viz[400001];
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 i=1;i<m;i++)
           if(A[i].c>A[i+1].c)
           {
             aux = A[i];
             A[i] = A[i+1];
             A[i+1] = aux;
             gata = 0;
           } 
     }
     while(!gata);
}

void parcurgere(void)
{
     int S = 0;
     int nr = 0;
     for(int i=1;i<=m && nr<n-1;i++)
     {
        if(!viz[A[i].x] || !viz[A[i].y])
        {
          A[i].t = 1;
          viz[A[i].x] = 1;
          viz[A[i].y] = 1;
          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)
          {
            A[i].t = 1;
            nr++;
            S += A[i].c;
          }  
     }
     fprintf(f,"%d ",S);
}

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

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