/* FILE: mst.cpp   last change: 30-Sep-2013   author: Fabio Bellini matricola: VR370413
 * Risoluzione del problema mst usando l'algoritmo di Kruskal.
 */

#define NDEBUG   // NDEBUG definita nella versione che consegno
#include <cassert>
#ifndef NDEBUG
#  include <iostream>  // uso di cin e cout non consentito in versione finale
#endif
#include <fstream>

using namespace std;

const int MAX_N = 10000;
const int MAX_M = 1000000;

int n;
int m;
int i,j,k,c;

int info_archi[MAX_M][4];
int archi_scelti[MAX_M][3];
int tot_peso=0;
int insiemi[MAX_N][MAX_N]; 
int conta[MAX_N];

//algoritmo di ordinamento
void ordina_archi(){
    for(i=1; i<=m;i++){
        for(j=1;j<=m-i;j++){
            if(info_archi[j][3]>info_archi[j+1][3]){
                int swap[4];
                swap[1]=info_archi[j][1];
                swap[2]=info_archi[j][2];
                swap[3]=info_archi[j][3];

                info_archi[j][1]=info_archi[j+1][1];
                info_archi[j][2]=info_archi[j+1][2];
                info_archi[j][3]=info_archi[j+1][3];

                info_archi[j+1][1]=swap[1];
                info_archi[j+1][2]=swap[2];
                info_archi[j+1][3]=swap[3];
            }
        }
    }

    return;
}

int cerca_rapp(int n){
    for(int i=1;i<=m;i++){
        for(int j=1;j<=conta[i];j++){
            if(n==insiemi[i][j])
                return i;
        }
    }
        return -1;
}

void kruskal(){
//creo gli insiemi singoletto
    for(i=1;i<=n;i++){
        insiemi[i][1]=i;
        conta[i]=1;
    }

    int n_scelte=1;
    for(i=1;i<=n;i++){
//cerco gli insiemi da unire partendo da quelli con peso minimo
        int nodo1=cerca_rapp(info_archi[i][1]);
        int nodo2=cerca_rapp(info_archi[i][2]);

        if(nodo1!=nodo2){ //se non sono già collegati
            archi_scelti[n_scelte][1]=info_archi[i][1];
            archi_scelti[n_scelte][2]=info_archi[i][2];
            n_scelte++;

            tot_peso += info_archi[i][3];
        
            //collego i due insiemi
            for(int j=1;j<=conta[nodo2];j++){
                conta[nodo1]++;
                insiemi[nodo1][conta[nodo1]]=insiemi[nodo2][j];
            }

            conta[nodo2]=0;
        }

    }

    return;
}

int main() {
    ifstream fin("input.txt"); assert( fin );
    fin>> n >> m;

    for(i=1;i<=m;i++){
        fin>>info_archi[i][1]>>info_archi[i][2]>>info_archi[i][3];
    }

    fin.close();

    ordina_archi();
    kruskal();

    ofstream fout("output.txt");
    fout<<tot_peso<<'\n';
    for(int i = 1; i <= n-1; i++)  
        fout << archi_scelti[i][1] << " "<< archi_scelti[i][2] <<'\n';
    fout.close();

    return 0;
  }