#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

#define INFINIT 1000000
#define MAX 500000

                    /* Varianta neoptimizata:  O(N^2) la cautarea unui nod nevizitat  */

struct PAIR{

    int vecin, cost;

};

ifstream fin("apm.in");
ofstream fout("apm.out");

int nrNoduri, nrMuchii, nodStart, costArborePartial, nrMuchiiArborePartial, vectorTati[MAX], vectorDistante[MAX];
bool vizitatNoduri[MAX];
vector <PAIR> listeAdiacenta[MAX];

void prim(){

    for ( int i = 1; i <= nrNoduri; i++){ //initializarea intiala a vectorilor
        vectorDistante[i] = INFINIT;
        vectorTati[i] = 0;
        vizitatNoduri[i] = false;
    }

    nodStart = 1; //plec de la nodul cu indicele cel mai mic
    vectorDistante[nodStart] = 0;

    int nrComponenteConexe = 1, nodCurent = 0;

    while ( nrComponenteConexe <= nrNoduri ){ //cat timp mai sunt noduri de prelucrat

              int distantaMinima = INFINIT;

              for ( int i = 1; i <= nrNoduri; i++){ //extrag nodul cu distanta minima ( dintre nodurile neprelucrate )
                        if ( !vizitatNoduri[i] ){ //daca nodul nu a fost prelucrat
                                if ( distantaMinima > vectorDistante[i] ){
                                    distantaMinima = vectorDistante[i];
                                    nodCurent = i;
                                }
                        }
              }

              costArborePartial += distantaMinima;

              if ( nodCurent != nodStart ) //muchia de la nodulStart la nodulStart nu se ia in calcul
                            nrMuchiiArborePartial++;

              vizitatNoduri[nodCurent] = true; //marchez nodul gasit ca fiind prelucrat

              int lim = listeAdiacenta[nodCurent].size();

              for ( int i = 0; i < lim; i++ ){ //actualizez distantele vecinilor neadaugati in APM

                    int vecin = listeAdiacenta[nodCurent][i].vecin;
                    int costVecin = listeAdiacenta[nodCurent][i].cost;

                    if ( !vizitatNoduri[vecin] && costVecin < vectorDistante[vecin] ){ //daca vecinul nu este deja adaugat in APM
                                                                                      // si distanta trebuie actualizata
                                vectorDistante[vecin] = costVecin;
                                vectorTati[vecin] = nodCurent;
                    }
              }

              nrComponenteConexe++;
    }

}

int main(){

    if ( !fin ){
        cout << "\nEroare la deschiderea fisierului !\n";
        exit(-1);
    }

    fin >> nrNoduri >> nrMuchii;

    for (int i = 1; i <= nrMuchii; i++){

            PAIR P;
            int x, y, cost;

            fin >> x >> y >> cost;

            P.vecin = y, P.cost = cost;
            listeAdiacenta[x].push_back(P);   //graf neorientat

            P.vecin = x;
            listeAdiacenta[y].push_back(P);

    }

    prim();

    fout << costArborePartial << "\n" << nrMuchiiArborePartial << "\n";

     for ( int i = 1; i <= nrNoduri; i++)
                if ( i != nodStart )
                        fout << i << " " << vectorTati[i] << "\n";

    return 0;

}