#include <fstream>
#include <iostream>
#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;
}
class disjointUnionSets{
    std::vector<int>rank,parinte;
    public:
    disjointUnionSets(int size){
        rank.resize(size+1);
        parinte.resize(size+1);
        for(int i=1;i<=size;i++){
            parinte[i]=i;
        }
    }
    int find(int i){
        int root=parinte[i];
        if(parinte[root]!=root){
            return parinte[root]=find(root);
        }
        return root;
    }
     void unionSets(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        if (xRoot == yRoot) return;
        if (rank[xRoot] < rank[yRoot]) {
            parinte[xRoot] = yRoot;
        } else if (rank[yRoot] < rank[xRoot]) {
            parinte[yRoot] = xRoot;
        } else {
            parinte[yRoot] = xRoot;
            rank[xRoot]++;
        }
    }
};
int main(){
    int n,m;
    fin>>n>>m;
    std::vector<muchie>listamuchii(m+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";
    // }
    int s=0,nrm=0;
    std::vector<std::vector<int>>solutie(m+1);
    disjointUnionSets dus(n);
    for(int k=1;k<=m;k++){
        if(dus.find(listamuchii[k].i)!=dus.find(listamuchii[k].j)){
            s+=listamuchii[k].cost;
            nrm++;
            dus.unionSets(listamuchii[k].i,listamuchii[k].j);
            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";
    }
    return 0;
}