#include<fstream>
#include<algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int Maxx=2e5+1;
struct NODE{
    int from,to,cost;
};
NODE A[Maxx];
int dad[Maxx];
int ord[Maxx];

bool compx(NODE a,NODE b){
    return a.cost<b.cost;
}
int get_dad(int son){
    if(dad[son]==son) return son;
    dad[son]=get_dad(dad[son]);
    return dad[son];
}
void unite(int x,int y){
    dad[get_dad(x)]=get_dad(y);
}

int main() {
    int n,m;
    fin>>n>>m;
    for(int i=1; i<=m; ++i){
        fin>>A[i].from>>A[i].to>>A[i].cost;
    }
    sort(A+1,A+m+1,compx);
    for(int i=1; i<=n; ++i) dad[i]=i;
    int ans=0;
    for(int i=1; i<=m; ++i){
        if(get_dad(A[i].from)!=get_dad(A[i].to)){
            ans+=A[i].cost;
            unite(A[i].from,A[i].to);
            ord[++ord[0]]=i;
        }
    }
    fout<<ans<<"\n"<<n-1<<"\n";
    for(int i=1; i<=n-1; ++i){
        fout<<A[ord[i]].from<<" "<<A[ord[i]].to<<"\n";
    }
    return 0;
}