#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
std::ifstream fin("apm.in");
std::ofstream fout("apm.out");
// struct muchie{
//     int i,j,cost;
// };
struct fcmp{
    bool operator()(std::pair<int,int> a, std::pair<int,int> b){
        return a.second>b.second;
    }
};
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<std::pair<int,int>,std::vector<std::pair<int,int>>,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({1,0});
    std::vector<int> solutie;
    while(!q.empty()){
        std::pair cap=q.top();
        if(viz[cap.first]==true){
            q.pop();
            continue;
        }
        viz[cap.first]=true;
        s+=cap.second;
        solutie.push_back(cap.first);
        //fout<<cap.first<<" "<<cap.second<<"\n";
        q.pop();
        for(auto vecinp: listavecini[cap.first]){
            if(!viz[vecinp.first])
                q.push(vecinp);
        }
    }
    fout<<s<<'\n';
    fout<<n-1<<'\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;
}