#include <cstdio>
#include <algorithm>
#define NMAX 200001
using namespace std;

int n,m,k,Sum;
int X[NMAX],Y[NMAX],C[NMAX],IND[NMAX],SOL[NMAX],father[NMAX];

bool order(const int &i,const int &j){
    return C[i]<C[j];
}

int root(int nod){

    if(father[nod] == nod) return nod;
    father[nod] = root(father[nod]);
    return father[nod];
}

void Adaug(int x,int y){

    father[root(x)] = root(y);
}

void read(){

    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=m;++i){
        scanf("%d%d%d",&X[i],&Y[i],&C[i]);
        IND[i] = i;
        father[i] = i;
 }
}

void solve(){


    sort(IND+1,IND+1+m,order);
    for(register int i=1;i<=m;++i)

        if(root(X[IND[i]]) != root(Y[IND[i]])){
            Sum+=C[IND[i]];
            Adaug(X[IND[i]],Y[IND[i]]);
            SOL[++k] = IND[i];
        }
}

void print(){

    printf("%d\n",Sum);
    printf("%d\n",k);
    for(register int i=1;i<=k;++i)
        printf("%d %d\n",X[SOL[i]],Y[SOL[i]]);
}

int main(){

    read();
    solve();
    print();

return 0;
}