#include <iostream>
#include <fstream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

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

class Graf{
private:
    int nrNoduri, nrMuchii;
    vector<tuple<int, int, int>> muchiiCost;
    vector<int> tata;
    vector<int> h;
    int gasesteReprez(const int &nr);
    int Apm(vector<pair<int, int>> &sol);
public:
    Graf(int nrNoduri, int nrMuchii) : nrNoduri(nrNoduri), nrMuchii(nrMuchii) {
        tata.resize(nrNoduri + 1, -1);
        h.resize(nrNoduri+ 1, 0);
    };
    void adaugaMuchie(const int &nod1, const int &nod2, const int &cost);
    void initializare(const int &nr);
    void reuneste(const int &x, const int &y);
    void afisareApm();
};

void Graf::adaugaMuchie(const int &nod1, const int &nod2, const int &cost) {
    muchiiCost.push_back(make_tuple(cost, nod1, nod2));
}

void Graf::initializare(const int &nr) {
    tata[nr] = 0;
    h[nr] = 0;
}

int Graf::gasesteReprez(const int &nr) {
    if (tata[nr] == 0)
        return nr;
    tata[nr] = gasesteReprez(tata[nr]);
    return tata[nr];
}

void Graf::reuneste(const int &x, const int &y) {
    int repX = gasesteReprez(x), repY = gasesteReprez(y);
    if(h[repX] > h[repY]){
        tata[repY] = repX;
    }
    else{
        tata[repX] = repY;
        if(h[repX] == h[repY])
            h[repY]++;
    }
}

void Graf::afisareApm() {
    vector<pair<int, int>> sol;

    fout << Apm(sol) << "\n" << sol.size() << "\n";

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

int Graf::Apm(vector<pair<int, int>> &sol) {
    int costApm = 0;

    for(int i = 1; i <= nrNoduri; i++){
        initializare(i);
    }

    sort(muchiiCost.begin(), muchiiCost.end());

    for(int i = 0; i < nrMuchii; i++){
        int x = get<1>(muchiiCost[i]);
        int y = get<2>(muchiiCost[i]);
        if(gasesteReprez(x) != gasesteReprez(y)){
            reuneste(x, y);
            int costCrt = get<0>(muchiiCost[i]);
            costApm += costCrt;
            sol.push_back({get<1>(muchiiCost[i]), get<2>(muchiiCost[i])});
        }
    }
    return costApm;
}


int main() {
    int noduri, muchii;
    fin>> noduri >> muchii;
    Graf G(noduri, muchii);
    for(int i = 0; i < muchii; i++){
        int n1, n2, cost;
        fin >> n1 >> n2 >> cost;
        G.adaugaMuchie(n1, n2, cost);
    }
    G.afisareApm();

    return 0;
}