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

using namespace std;

#define INFINIT 1000000

typedef pair<int,int> MUCHIE; //pentru perechile de muchii x,y

struct PAIR{

    int vecin, cost;

};

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

int nrNoduri, nrMuchii, nodStart, costArborePartial, *vectorTati;
bool *vizitatNoduri;
vector <PAIR> *listeAdiacenta;
vector < pair<int,int> > muchiiArborePartial; //stochez muchiile APM - ului
priority_queue < pair<int,MUCHIE> > heapMuchii; //va fi un min heap ( in care comparatia o fac pe baza distantei )
                                                // iar structura unei componente este ( distanta , muchie (x,y) )

void prim(){

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

    nodStart = 1; //pornesc de la nodul cu indicele cel mai mic

    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

              //extrag datele muchiei curente
              int distantaMinima = -heapMuchii.top().first; // extrag cu "-" pt ca am introdus cu "-" --> vreau min heap
              int vecin = heapMuchii.top().second.second; //extrag nodul y din perechea (x,y)
              nodCurent = heapMuchii.top().second.first; //extrag nodul x din perechea (x,y)

              heapMuchii.pop(); //elimin muchia din heap

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

              vizitatNoduri[vecin] = true; //altfel marchez noul nod din APM

              costArborePartial += distantaMinima;

              muchiiArborePartial.push_back(make_pair(nodCurent,vecin)); //adaug muchia in APM ( stiu ca in momentul curent este o muchie valida )

              lim = listeAdiacenta[vecin].size();

              for ( int i = 0; i < lim; i++ ) //adaug muchiile vecinului in heap
                    if ( !vizitatNoduri[listeAdiacenta[vecin][i].vecin] ) //verific ca nodul adiacent sa nu fie vizitat , deoarece daca este vizitat exista deja in APM
                         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;
    vizitatNoduri = NULL;
    listeAdiacenta = NULL;

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

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

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

    int lim = muchiiArborePartial.size();

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



    return 0;

}