#include <stdlib.h>
#include <stdio.h>

int no_arco=1048577;    // peso oltre il limite che serve ad indicare che non esiste un arco

typedef struct nodi{
    int numero_nodo;    
    int peso;
} t_grafo;  // struttura che descrive i nodi del grafo

typedef struct arco{
    int dx;    
    int sx;
} t_arco;   // struttura che descrive gli estremi degli archi del grafo

int ordina(const void *a, const void *b)    // funzione che ordina in modo crescente il peso dei nodi figli
{
    t_grafo na =*(t_grafo *)a;
    t_grafo nb =*(t_grafo *)b;

    if(na.peso>nb.peso) return 1;
    if(na.peso<nb.peso) return -1;
    
    if(na.numero_nodo>nb.numero_nodo) return 1;
    if(na.numero_nodo<nb.numero_nodo) return -1;

    return 0;
}

int ordina_archi(const void *a, const void *b) // funzione che ordina gli archi per l'output
{
    t_arco aa =*(t_arco *)a;
    t_arco ab =*(t_arco *)b;

    if(aa.dx>ab.dx) return 1;
    if(aa.dx<ab.dx) return -1;

    if(aa.sx>ab.sx) return 1;
    if(aa.sx<ab.sx) return -1;

    return 0;
}

t_grafo grafo[10000][10000];    // matrice di adiacenza che descrive il grafo

int N, M;
t_arco archi[1000000];  // archi presenti nel grafo
int num_archi=0;
int inserito[10000];    // vettore che serve a tenere il conto dei nodi già raggiunti dall'albero
int peso_tot;   // peso dell'albero in output

void check(int precedente)  // funzione di controllo per verificare se è rimasto un nodo isolato
{
    if(inserito[precedente]==0)
    {
         int i;
         t_grafo ramo[N];

         for (i=0; i<N; i++)
         {
            ramo[i].numero_nodo=grafo[precedente][i].numero_nodo;
            ramo[i].peso=grafo[precedente][i].peso;
         }

        qsort(ramo,N,sizeof(t_grafo),ordina);

        int min, max, tmp;
        min=precedente+1; max=ramo[0].numero_nodo;
        if(min > max) { tmp=max; max=min; min=tmp;}        
        archi[num_archi].dx=min; 
        archi[num_archi].sx=max;
        num_archi++;
        peso_tot=peso_tot+ramo[0].peso;
    }
    return;
}

void calcola_albero(int padre, int start)   // funzione per la costruzione dell'albero
{
         int i;
         int c=0;
         t_grafo ramo[N-start];

         inserito[start-1]=1;

         if (start!=N){
             for (i=start; i<N; i++)
             {
                ramo[c].numero_nodo=grafo[start-1][i].numero_nodo;
                ramo[c].peso=grafo[start-1][i].peso;
                c++;
             }

            qsort(ramo,c,sizeof(t_grafo),ordina);

            if(ramo[0].peso != no_arco)
            {
                if(ramo[0].peso<grafo[padre-1][ramo[0].numero_nodo-1].peso)
                {
                    archi[num_archi].dx=start; 
                    archi[num_archi].sx=ramo[0].numero_nodo;
                    num_archi++;
                    peso_tot=peso_tot+ramo[0].peso;
                    check(start-2);
                    calcola_albero(start,ramo[0].numero_nodo);
                }
                else
                {
                    archi[num_archi].dx=padre; 
                    archi[num_archi].sx=grafo[padre-1][(ramo[0].numero_nodo)-1].numero_nodo;
                    num_archi++;
                    peso_tot=peso_tot+grafo[padre-1][(ramo[0].numero_nodo)-1].peso;
                    check(start-2);
                    calcola_albero(padre,ramo[0].numero_nodo);
                }
            }
         }
         return;
}

int main()
{
    int i,j,p,f,w;    
    
    FILE *fr = fopen("input.txt","r");
    FILE *fw = fopen("output.txt","w");
    
    fscanf(fr,"%d",&N);
    fscanf(fr,"%d",&M);
    
    t_grafo figli[N]; 

    for(i=0; i<N; i++)
    {
        for(j=0; j<N; j++)
        {
            grafo[i][j].numero_nodo=j+1;
            grafo[i][j].peso=no_arco;           
        }        
    }

    for(i=0; i<M; i++)
    {
         fscanf(fr,"%d",&p);
         fscanf(fr,"%d",&f);
         fscanf(fr,"%d",&w);

         grafo[p-1][f-1].peso=w;
         grafo[f-1][p-1].peso=w;      
    }

    for(j=0; j<N; j++)
    {
        figli[j].numero_nodo=grafo[0][j].numero_nodo;
        figli[j].peso=grafo[0][j].peso;
        inserito[j]=0;   
    }
          
    qsort(figli,N,sizeof(t_grafo),ordina);

    archi[num_archi].dx=1;
    archi[num_archi].sx=figli[0].numero_nodo;
    num_archi++;
    peso_tot=grafo[0][figli[0].numero_nodo-1].peso;

    inserito[0]=1;

    calcola_albero(1,figli[0].numero_nodo);

    qsort(archi,num_archi,sizeof(t_arco),ordina_archi);
    fprintf(fw,"%d\n",peso_tot);
    for(i=0; i<num_archi; i++)
    {
        fprintf(fw,"%d %d\n",archi[i].dx,archi[i].sx);
    }

    fflush(fr);
    fclose(fr);

    fflush(fw);
    fclose(fw);

    exit(0);
}