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

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

vector<int> vectorCulori;
int nrMuchii;
int nrNoduri;

int reprezentant(int x){
     return vectorCulori[x];
}


void reunire(int x, int y){
    int rx = reprezentant(x);
    int ry = reprezentant(y);
    for(int i=1;i<=nrNoduri;i++)
        if (vectorCulori[i]==rx)
            vectorCulori[i]=ry;

}

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++){
        vectorCulori[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;

    fin >> nrNoduri;

    fin >> nrMuchii;

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

    vectorCulori.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;
}