#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

#define DIM 200001



int X[DIM],Y[DIM],cost[DIM],parent[DIM],ind[DIM];
std::vector<int> sol;
int n,m,sum=0;
std::ifstream f("apm.in");
std::ofstream g("apm.out");

void read(){
    f>>n>>m;
    for(int i=0;i<=m;i++){
        f>>X[i]>>Y[i]>>cost[i];
        ind[i]=i;
    }
    for(int i=1;i<=n;i++)
        parent[i]=i;
    std::sort(ind,ind+m,[&](int x, int y){
        return cost[x]<cost[y];
    });
    f.close();
}

int find_parent(int x){
    if(parent[x]==x)
        return x;
    return find_parent(parent[x]);
}

void unite(int x, int y){
    parent[find_parent(y)]=find_parent(x);
}

bool formCycle(int x, int y){
    return find_parent(x)==find_parent(y);
}

void krukal(){
    for(int i=0;i<m;i++){
        if(!formCycle(X[ind[i]],Y[ind[i]])){
            sol.push_back(ind[i]);
            unite(X[ind[i]],Y[ind[i]]);
            if(sol.size()==n-1) break;
        }
    }
    for(int i:sol){
        sum+=cost[i];
    }
}

void print(){
    g<<sum<<"\n"<<n-1<<"\n";
    for(int i:sol){
        g<<X[i]<<" "<<Y[i]<<"\n";
    }
}
int main() {
    read();
    krukal();
    print();
    return 0;
}