#include <cstdio>
#include <algorithm>
using namespace std;


struct edge{int a;
            int b;
            int cost;
            };

edge G[400005],sol[200000];
int minim,maxim,i,j,num,n,m,tata[1000],h[1000];
int c;

void combine_Heap(int rad,int n){
    int tata,fiu;
    edge x=G[rad];
    tata=rad;
    fiu=rad*2;

    while(fiu<=n){
        if(fiu+1<=n)
        if(G[fiu].cost>G[fiu+1].cost){

            fiu=fiu+1;

        }
        if(x.cost>G[fiu].cost){

            G[tata]=G[fiu];
            tata=fiu;
            fiu=2*tata;

        }
        else{
            break;

        }

    }
    G[tata]=x;

}

edge extractmin(int &n){

    edge x=G[1];

    G[1]=G[n];
    --n;
    combine_Heap(1,n);
    return x;

}
int find(int x){

    int rad,aux;

    rad=x;

    while(tata[rad]){

        rad=tata[rad];

    }
    while(tata[x]){

        aux=x;
        x=tata[x];
        tata[aux]=rad;

    }

    return rad;

}
void uni(int a,int b){

    if(h[b]>h[a]){

        tata[a]=b;

    }
    else{

        tata[b]=a;
        if(h[a]==h[b])

            ++h[a];

    }

}
int main()
{
    freopen("kruskal.in","r",stdin);
    freopen("kruskal.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;++i){

        scanf("%d%d%d",&G[i].a,&G[i].b,&G[i].cost);
    }
    for(i=m/2;i>0;--i){

        combine_Heap(i,m);

    }
    int f1,f2;
    while(num<n-1){

        edge muchie=extractmin(m);

        f1=find(muchie.a);
        f2=find(muchie.b);

        if(f1!=f2){

            sol[++num]=muchie;
            c+=muchie.cost;
            uni(f1,f2);

        }
    }
    if(num<n-1) {fclose(stdout);
    freopen("apm.out","w",stdout);printf("GRAFUL NU ESTE CONEX");}
    else{
    printf("%lld\n%d\n",c,num);
    for(i=1;i<=n-1;++i){

        printf("%d %d\n",sol[i].a,sol[i].b);

    }
    }
    return 0;
}