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

int n,m,k;
int C[NMAX];
int Sol[NMAX];
int X[NMAX];
int Y[NMAX];
int father[NMAX];
int depth[NMAX];
int IND[NMAX];
int cost;

bool compare(const int &i,const int &j){

    return C[i] < C[j];
}

int root(int node){

    while(father[node])
        node = father[node];

return node;
}

void compose(int x,int y){

    x = root(x);
    y = root(y);

        if(depth[x] > depth[y]){

            father[y] = x;
            ++depth[x];
        }

        else if(depth[y] > depth[x]){

            father[x] = y;
            ++depth[y];
        }
        else {

            father[x] = y;
            ++depth[y];
    }
}

void solve(){

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

    sort(IND+1,IND+m+1,compare);

    for(register int i=1;i<=m;++i)

        if(root(X[IND[i]])!=root(Y[IND[i]])){

            compose(X[IND[i]],Y[IND[i]]);
            cost += C[IND[i]];
            Sol[++k] = IND[i];
        }
}

void write(){

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

int main(){

    solve();
    write();

return 0;
}