#include <cassert>
#include <fstream>

using namespace std;


const int MAX_N = 10000;
double A[MAX_N+1][MAX_N+1];

int n,m;


int main(){

  /*Acquisisco l'input in matrice*/
  ifstream fin("input.txt"); assert( fin );
  fin >> n >> m;
  
  int vetTmp[1][2];
  double val;

  for( int i = 0; i < m; i++){
     fin >> vetTmp[0][0] >> vetTmp[0][1] >> val;
     A[0][i] = i;
     A[i][0] = i;
     A[vetTmp[0][0]][vetTmp[0][1]] = val;
     A[vetTmp[0][1]][vetTmp[0][0]] = val;
  }
  A[1][0] = 1;

  fin.close();

  /* Fine acquisizione input*/

 
  /*Ciclo sulla sottodiagonale
  for(int i = 1; i <= n; i++){
     for(int j = 1  ; j < i; j++){
        A[i][j] = 99;
     }
  }
  
 for(int i = 0; i <= n; i++){
     for(int j = 0; j <= n; j++){
        printf("%g ",A[i][j]);
     }
     printf("\n");
  }
  */

  /*Inizio la procedura*/
   
  int listaNodiRaggiunti[MAX_N+1];
  listaNodiRaggiunti[1] = 1;
  int countLista = 1;
  double valMin = (2^20)+1;
  int tracciamento[2];
  tracciamento[0] = 0; //Riga
  tracciamento[1] = 0; //Colonna
  
  int soluzioneArchi[MAX_N][2];
  double soluzioneValore = 0;  


  /*Ciclo finche non raggiungo tutti i nodi*/
  while(countLista != n){
     
    /*Cerco l arco di valore minimo per raggiungere un altro nodo da quelli gia' raggiunti*/
    for(int i = 1; i <= countLista; i++){ 
        /*Controllo solo la sopradiagonale*/
        for(int j = listaNodiRaggiunti[i]; j <= n; j++){
           if(A[listaNodiRaggiunti[i]][j] < valMin && A[listaNodiRaggiunti[i]][j] != 0){
             valMin = A[listaNodiRaggiunti[i]][j];
             tracciamento[0] = listaNodiRaggiunti[i];
             tracciamento[1] = j;
           }
        }
    }
    
    /*Setto la soluzione parziale*/
    
    soluzioneArchi[tracciamento[1]][0] = tracciamento[0];
    soluzioneArchi[tracciamento[1]][1] = tracciamento[1];
    soluzioneValore += valMin;
    listaNodiRaggiunti[++countLista] = tracciamento[1];

    /*Cancello tutti gli altri percorsi per quel nodo da altri nodi*/

    for(int y = 0; y < tracciamento[1]; y++)
       A[y][tracciamento[1]] = 0; 

    /*Resetto valMIn*/
    valMin = (2^20)+1;

 

  
  } /*Fine while*/
  
  ofstream fout("output.txt");
  fout << soluzioneValore << "\n";
   
  for(int y = 2; y <= n; y++){
     fout << soluzioneArchi[y][0] << soluzioneArchi[y][1] << "\n";
  }
  fout << endl;
  fout.close();

  return 0;

}







 /* stampe


     for(int i = 0; i <= n; i++){
     for(int j = 0; j <= n; j++){
        printf("%g ",A[i][j]);
     }
     printf("\n");
  }

  

  



    printf("%d%d  %d",tracciamento[0],tracciamento[1],countLista);
    
    for(int y = 1; y<=n; y++){
       printf("  %d",listaNodiRaggiunti[y]);
    } 

    printf("\n");
  */