#include <bits/stdc++.h>

int v[200001];
int sz[200001];
int in=1;

typedef struct{
    int a;
    int b;
    int c;
} muc;

muc d[400000];

int compare(const void*a,const void*b){
    muc x=*(muc*)a;
    muc y=*(muc*)b;
    return x.c-y.c;
}

int get(int k){
    if(v[k]==0)
        return k;
    v[k]=get(v[k]);
    return v[k];
}

void mrg(int a,int b){
    a=get(a);
    b=get(b);
    if(sz[a]<sz[b]){
        a+=b;
        b=a-b;
        a=a-b;
    }
    v[b]=a;
    sz[a]+=sz[b];
    if(sz[a]>in)
        in=sz[a];
}

int afis[400000][2];

int main()
{
    int n,m,i,sum=0,a,b,k=0;
    FILE*fi,*fo;
    fi=fopen("apm.in","r");
    fo=fopen("apm.out","w");
    fscanf(fi,"%d%d",&n,&m);
    for(i=0;i<m;i++){
        fscanf(fi,"%d%d%d",&d[i].a,&d[i].b,&d[i].c);
    }
    for(i=1;i<=n;i++){
        sz[i]=1;
    }
    qsort(d,m,sizeof(muc),compare);
    i=0;
    while(in<n){
        a=d[i].a;
        b=d[i].b;
        if(get(a)!=get(b))
        {
            afis[k][0]=a;
            afis[k][1]=b;
            k++;
            sum+=d[i].c;
            mrg(a,b);
        }
        i++;
    }
    fprintf(fo,"%d\n%d\n",sum,k);
    for(i=0;i<k;i++){
        fprintf(fo,"%d %d\n",afis[i][0],afis[i][1]);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}