#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],rang[NMAX];

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

int root(int nod){

    while(father[nod]) nod = father[nod];
    return nod;
}

void Adaug(int x,int y){

    int v1 = root(x);
    int v2 = root(y);
    if(rang[v1] = rang[v2]){

        father[v1] = v2;
        rang[v2]++;
    }
    else if(rang[v1] < rang[v2])
            father[v1] = v2;
          else father[v2] = v1;
}

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;
        rang[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;
}