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

using namespace std;

#define INFINIT 1000000

struct PAIR{

    int vecin, cost;

};

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

int nrNoduri, nrMuchii, nodStart, costArborePartial, nrMuchiiArborePartial, *vectorTati, *vectorDistante;
bool *vizitatNoduri;
vector <PAIR> *listeAdiacenta;
priority_queue < pair<int,int> > heapMuchii; //va fi un min heap


void prim(){

    int nodCurent = 0;

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

    for ( int i = 0; i < lim; i++ ){ //adaug in heap muchiile adiacente cu nodul de start
            heapMuchii.push(make_pair(-listeAdiacenta[nodStart][i].cost,listeAdiacenta[nodStart][i].vecin));
            vectorTati[listeAdiacenta[nodStart][i].vecin] = nodStart; // si actualizez vectorul de tati pt nodurile adiacente
    }

    while ( !heapMuchii.empty() ){ //cat timp mai sunt noduri de prelucrat

              int distantaMinima = -heapMuchii.top().first; // extrag cu "-" pt ca am introdus cu "-" --> vreau min heap
              int vecin = heapMuchii.top().second;
              nodCurent = vectorTati[vecin];

              heapMuchii.pop();

              vizitatNoduri[nodCurent] = true;

              if ( vizitatNoduri[vecin] ) //daca vecinul este vizitat inseamna ca exista in APM , deci continuam cu extargerea urmatoare muchi
                                    continue;

              costArborePartial += distantaMinima;

              nrMuchiiArborePartial++;

              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;
                    }
              }

              lim = listeAdiacenta[vecin].size();

              for ( int i = 0; i < lim; i++ ){ //adaug muchiile vecinului in heap
                     heapMuchii.push(make_pair(-listeAdiacenta[vecin][i].cost,listeAdiacenta[vecin][i].vecin));
                     vectorTati[listeAdiacenta[vecin][i].vecin] = vecin; // si actualizez vectorul de tati pt nodurile adiacente
              }

    }

}

int main(){

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

    fin >> nrNoduri;

    vectorTati = NULL;
    vectorDistante = NULL;
    vizitatNoduri = NULL;
    listeAdiacenta = NULL;

    vectorTati = new int[nrNoduri + 5];
    vectorDistante = new int[nrNoduri + 5];
    vizitatNoduri = new bool[nrNoduri + 5];
    listeAdiacenta = new vector <PAIR> [nrNoduri + 5];

    if (!vectorTati || !vectorDistante || !vizitatNoduri || !listeAdiacenta){
        cout << "\nEroare la alocarea dinamica !\n";
        exit(-1);
    }

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

    nodStart = 1;
    vectorDistante[nodStart] = 0;

    fin >> 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;

}