#include <fstream>
#include <vector>
#include <algorithm>
std::ifstream fin("apm.in");
std::ofstream fout("apm.out");
struct muchie{
    int i, j, cost;
};
bool comp(muchie a, muchie b){
    return a.cost<b.cost;
}
int main(){
    int n,m;
    fin>>n>>m;
    std::vector<muchie>listamuchii(m+1);
    std::vector<int>reprezentanti(n+1);
    for(int k=1;k<=m;k++){
        fin>>listamuchii[k].i>>listamuchii[k].j>>listamuchii[k].cost;
    }
    std::sort(listamuchii.begin()+1,listamuchii.end(),comp);
    // for(auto muchie:listamuchii){
    //     fout<<muchie.i<<" "<<muchie.j<<" "<<muchie.cost;
    //     fout<<"\n";
    // }
    for(int i=1;i<=n;i++){
        reprezentanti[i]=i;
    }
    // for(int i=0;i<n;i++){
    //     fout<<reprezentanti[i]<<" ";
    // }
    int s=0,nrm=0;
    std::vector<std::vector<int>>solutie(m+1);
    for(int k=1;k<=m;k++){
        if(reprezentanti[listamuchii[k].i]!=reprezentanti[listamuchii[k].j]){
            s+=listamuchii[k].cost;
            nrm++;
            int ri=reprezentanti[listamuchii[k].i],rj=reprezentanti[listamuchii[k].j];
            for(int o=1;o<=n;o++){
                if(reprezentanti[o]==rj){
                    reprezentanti[o]=ri;
                }
            }
            solutie[nrm].push_back(listamuchii[k].i);
            solutie[nrm].push_back(listamuchii[k].j);
        }
    }
    fout<<s<<"\n";
    fout<<nrm<<"\n";
    for(int i=1;i<=nrm;i++){
        for(auto nr:solutie[i]){
            fout<<nr<<" ";
        }
        fout<<"\n";
    }

}