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

using namespace std;

#define INFINIT 1000000

typedef pair<int,int> MUCHIE;

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;
vector < pair<int,int> > muchiiDeAfisat;
priority_queue < pair<int,MUCHIE> > 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,make_pair(nodStart,listeAdiacenta[nodStart][i].vecin)));

    vizitatNoduri[nodStart] = true;

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

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

             // cout << nodCurent << " " << vecin << " " << distantaMinima << "\n";

              heapMuchii.pop();

              //vizitatNoduri[nodCurent] = true;

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

              vizitatNoduri[vecin] = true;

              costArborePartial += distantaMinima;

              nrMuchiiArborePartial++;

              muchiiDeAfisat.push_back(make_pair(nodCurent,vecin)); //daca am o muchie valida o adaug
/*
              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
                    if ( !vizitatNoduri[listeAdiacenta[vecin][i].vecin] )
                         heapMuchii.push(make_pair(-listeAdiacenta[vecin][i].cost,make_pair(vecin,listeAdiacenta[vecin][i].vecin)));
    }

}

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" << muchiiDeAfisat.size() << "\n";

    for ( int i = 0; i < muchiiDeAfisat.size(); i++)
        fout << muchiiDeAfisat[i].first << " " << muchiiDeAfisat[i].second << "\n";



    return 0;

}