#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <utility>
std::ifstream fin("apm.in");
std::ofstream fout("apm.out");
struct muchie{
    int i,j,cost;
};
struct fcmp{
    bool operator()(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<std::vector<std::pair<int,int>>>listavecini(n+1);
    std::priority_queue<muchie,std::vector<muchie>,fcmp>q;
    std::vector<bool>viz(n+1);
    int x,y,c;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>c;
        listavecini[x].push_back({y,c});
        listavecini[y].push_back({x,c});

        //fin>>listamuchii[i].i>>listamuchii[i].j>>listamuchii[i].cost;
    }
    int s=0;
    q.push({0,1,0});
    std::vector<std::pair<int,int>> solutie;
    while(!q.empty()){
        muchie cap=q.top();
        if(viz[cap.j]==true){
            q.pop();
            continue;
        }
        viz[cap.j]=true;
        s+=cap.cost;
        solutie.push_back({cap.i,cap.j});
        //fout<<cap.i<<" "<<cap.j<<"\n";
        q.pop();
        for(auto vecinp: listavecini[cap.j]){
            if(!viz[vecinp.first])
                {
                    q.push({cap.j,vecinp.first,vecinp.second});
                }
        }
    }

    fout<<s<<'\n';
    fout<<n-1<<'\n';
    for(int i=1;i<=n-1;i++){
        fout<<solutie[i].first<<" "<<solutie[i].second<<'\n';
    }
    // for(int i=2;i<=n;i++){
    //     fout<<i<<" "<<tati[i]<<'\n';
    // }
    // for(int i=0;i<solutie.size()-1;i++){
    //     fout<<solutie[i]<<" "<<solutie[i+1]<<'\n';
    // }
    // for(int i=1;i<=m;i++){
    //     fout<<listamuchii[i].i<<" "<<listamuchii[i].j<<" "<<listamuchii[i].cost<<"\n";
    // }
    
    return 0;
}