#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#define dim 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,i,j,x[dim],y[dim],poz[dim],c[dim],pad[dim],k,X,Y,sol;
vector<int> v;
int cmp(int a, int b){
    return c[a]<c[b];
}
int pmd(int i){
    if(pad[i]<0){
        return i;
    }
    pad[i]=pmd(pad[i]);
    return pad[i];
}
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x[i]>>y[i]>>c[i];
        poz[i]=i;
    }
    memset(pad,-1,sizeof(pad));
    sort(poz+1,poz+m+1,cmp);
    for(i=1;i<=m;i++){
        k=poz[i];
        X=pmd(x[k]);
        Y=pmd(y[k]);
        if(X!=Y){
            sol+=c[k];
            pad[X]=Y;
            v.push_back(k);
        }

    }
    fout<<sol<<"\n";
    fout<<n-1<<"\n";
    for(i=0;i<n-1;i++){
        fout<<x[v[i]]<<" "<<y[v[i]]<<"\n";
    }

    return 0;
}