#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

class graf{
protected:
    int NrMuchii, NrNoduri;
    bool eOrientat;
    vector<vector<int>> adiacenta;

public:
    graf(int NrNod = 0, int NrMuc = 0, bool orientat = false, vector<vector<int>> adiacenta = {}){
        this->NrNoduri = NrNod;
        this->NrMuchii = NrMuc;
        this->eOrientat = orientat;
    }
    ~graf(){
        this->NrNoduri = 0;
        this->NrMuchii = 0;
    }
    void setNrNoduri(int&);
    void setNrMuchii(int&);
    void setMuchii(int, int);
    int getNrNoduri();
    int getNrMuchii();
    void citireMuchii();
    void BFS(int, bool[], int[]);
    void DFS(int, bool[]);
    int NrComponenteConexe(bool[]);
    int gaseste(int, vector<int> &);
    void uneste(int, int, vector<int> &);
    vector<int> disjoint(vector<pair<int, pair<int, int>>>);
};

class grafCuCost : public graf
{
private:
    vector<vector<int>> costMuchii;

public:
    grafCuCost(int NrNoduri = 0, int NrMuchii = 0, bool orientat = false, vector<vector<int>> adiacenta = {}, vector<vector<int>> costMuchii = {}) : graf(NrNoduri, NrMuchii, orientat, adiacenta)
    {
        this->costMuchii = costMuchii;
    }
    vector<vector<int>> apm(vector<int> &, int &);
};

void graf::setNrNoduri(int &n){
    NrNoduri = n;
}

void graf::setNrMuchii(int &m){
    NrMuchii = m;
}

void graf::setMuchii(int nod1, int nod2){
    adiacenta[nod1].push_back(nod2);
}

int graf::getNrNoduri(){
    return NrNoduri;
}

int graf::getNrMuchii(){
    return NrMuchii;
}

void graf::citireMuchii(){
    int n1, n2;
    adiacenta.resize(NrNoduri + 1);
    for(int i = 0; i < NrMuchii; i++){
        in>>n1>>n2;
        setMuchii(n1, n2);
        if(!eOrientat){
            setMuchii(n2, n1);
        }
    }
}

void graf::BFS(int NodSursa, bool vizitat[], int distanta[]){
    queue<int> coada;
    coada.push(NodSursa);
    vizitat[NodSursa] = true;
    while(!coada.empty()){
        for(int nod : adiacenta[coada.front()]){
            if(!vizitat[nod]){
                vizitat[nod] = true;
                coada.push(nod);
                distanta[nod] = distanta[coada.front()] + 1;
            }
        }
        coada.pop();
    }
    for(int nod = 1; nod <= NrNoduri; nod++){
        if((NodSursa != nod) && (distanta[nod] == 0)){
            out<<"-1 ";
        }
        else{
            out<<distanta[nod]<<" ";
        }
    }
}

void graf::DFS(int Nod, bool vizitat[]){
    vizitat[Nod] = true;
    for(int vecin : adiacenta[Nod]){
        if(!vizitat[vecin]){
            DFS(vecin, vizitat);
        }
    }
}

int graf::NrComponenteConexe(bool vizitat[]){
    int NrCompCon = 0;
    for(int Nod = 1; Nod <= NrNoduri; Nod++){
        if(!vizitat[Nod]){
            NrCompCon++;
            DFS(Nod, vizitat);
        }
    }
    return NrCompCon;
}

int graf::gaseste(int nod, vector<int> &radacina){
    if(radacina[nod] != nod){
        radacina[nod] = gaseste(radacina[nod], radacina);
    }
    return radacina[nod];
}

void graf::uneste(int x, int y, vector<int> &radacina){
    int rad1, rad2;
    rad1 = gaseste(x, radacina);
    rad2 = gaseste(y, radacina);
    radacina[rad1] = rad2;
}

vector<int> graf::disjoint(vector<pair<int,pair<int, int>>> operatii){
    vector<int> radacina(NrNoduri + 1);
    vector<int> rez;
    for(int i = 0; i < NrNoduri; i++){
        radacina[i] = i;
    }
    for(int i = 0; i < operatii.size(); i++){
        int cod = operatii[i].first;
        int x = operatii[i].second.first;
        int y = operatii[i].second.second;
        if(cod == 1){
            uneste(x, y, radacina);
        }
        else{
            if(cod == 2){
                if(gaseste(x, radacina) == gaseste(y, radacina)){
                    rez.push_back(1);
                }
                else{
                    rez.push_back(0);
                }
            }
        }
    }
    return rez;
}

bool compara(vector<int> v1, vector<int> v2){
    return v1[2] < v2[2];
}

vector<vector<int>> grafCuCost::apm(vector<int> &parinte, int &costTotal){
    vector<vector<int>> rez;
    int nod1, nod2, p1, p2, i = 0;
    sort(costMuchii.begin(), costMuchii.end(), compara);
    while(rez.size() < NrNoduri - 1){
        nod1 = costMuchii[i][0];
        nod2 = costMuchii[i][1];
        p1 = nod1;
        p2 = nod2;
        p1 = gaseste(nod1, parinte);
        p2 = gaseste(nod2, parinte);
        if(p1 != p2){
            if(p1 < p2){
                parinte[p1] = parinte[p2];
            }
            else{
                parinte[p2] = parinte[p2];
            }
            rez.push_back({nod1, nod2});
            costTotal += costMuchii[i][2];
        }
        i++;
    }
    return rez;
}

void InfoArena_BFS(){
    int N, M, Sursa;
    in>>N>>M>>Sursa;
    graf G(N, M, true);
    G.citireMuchii();
    bool vizitat[N + 1] = {false};
    int distanta[N + 1] = {0};
    G.BFS(Sursa, vizitat, distanta);
}

void InfoArena_DFS(){
    int N, M;
    in>>N>>M;
    graf G(N, M, false);
    G.citireMuchii();
    bool vizitat[N + 1] = {false};
    out<<G.NrComponenteConexe(vizitat);
}

void InfoArena_disjoint(){
    int N, M, cod, x, y;
    in>>N>>M;
    graf G(N, 0, false);
    vector<pair<int, pair<int, int>>> operatii;
    for(int i = 0; i < M; i++){
        in>>cod>>x>>y;
        operatii.push_back(make_pair(cod, make_pair(x, y)));
    }
    vector<int> rez = G.disjoint(operatii);
    for(int i = 0; i < rez.size(); i++){
        if(rez[i]){
            out<<"DA"<<"\n";
        }
        else{
            out<<"NU"<<"\n";
        }
    }
}

void InfoArena_apm(){
    int N, M, X, Y, C;
    in>>N>>M;
    vector<vector<int>> adiacenta(N + 1, {0});
    vector<vector<int>> costMuchii;
    for(int i = 0; i < M; i++){
        in>>X>>Y>>C;
        costMuchii.push_back({X, Y, C});
    }
    grafCuCost G(N, M, false, adiacenta, costMuchii);
    vector<int> parinte(N + 1);
    for(int i = 0; i < parinte.size(); i++){
        parinte[i] = i;
    }
    int costTotal = 0;
    vector<vector<int>> rez = G.apm(parinte, costTotal);
    out<<costTotal<<"\n"<<rez.size()<<"\n";
    for(int i = 0; i < rez.size(); i++){
        out<<rez[i][0]<<" "<<rez[i][1]<<"\n";
    }

}

int main()
{
    //InfoArena_BFS();
    //InfoArena_DFS();
    //InfoArena_disjoint();
    InfoArena_apm();
    return 0;
}