#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

vector<int> vectorTati;
vector<int> vectorInaltimi;

int reprezentant(int x){
    if(vectorTati[x] == 0){
        return x;
    }
    else{
        vectorTati[x] = reprezentant(vectorTati[x]);
        return vectorTati[x];
    }
}


void reunire(int x, int y){
    x = reprezentant(x);
    y = reprezentant(y);
    if(vectorInaltimi[x] < vectorInaltimi[y]){
        vectorTati[x] = y;
    }
    else if(vectorInaltimi[x] == vectorInaltimi[y]){
        vectorTati[x] = y;
        vectorInaltimi[y]++;
    }
    else{
        vectorTati[y] = x;
    }

}

vector<vector<int>> kruskal(vector<vector<int>> m, int nrNoduri){ //un element din m este un vector cu 3 elemente: cost, x,y (!!cost primul, pentru sortare)
    for(int i=0; i<nrNoduri; i++){
        vectorTati[i] = 0;
    }
    for(int i=0; i<nrNoduri; i++){
        vectorInaltimi[i] = 0;
    }

    sort(m.begin(), m.end());
    vector<vector<int>> rezultat;
    for(auto muchie : m){
       
        if(reprezentant(muchie[1]) != reprezentant(muchie[2])){
            reunire(muchie[1], muchie[2]);
            rezultat.push_back(muchie);
            if(rezultat.size() >= nrNoduri-1){
                break;
            }
           }
    }
    return rezultat;
}






int main()
{
    vector<vector<int>> m;
    int nrNoduri;
    fin >> nrNoduri;
    int nrMuchii;
    fin >> nrMuchii;

    for(int i=0; i<nrMuchii; i++){
        int cost, x, y;
        fin >> x >> y >> cost;
        m.push_back({cost, x, y});
    }

    vectorTati.assign(nrNoduri + 1,0);
    vectorInaltimi.assign(nrNoduri+1,0);

    vector<vector<int>> rez;
    rez = kruskal(m, nrNoduri);

    int s = 0;
    for(auto& muc : rez){
        s = s + muc[0];
    }
    fout << s << '\n';
    fout << rez.size() << '\n';
    for(auto& muc : rez){
        fout << muc[1] << " " << muc[2] << '\n';
    }
    fout.close();

    return 0;
}