#include<cstdio>
#include<algorithm>

using namespace std;

int t[400001];

int i,rx,ry,cost,selectate,n,m;

struct muchie{

    int x;
    int y;
    int c;

}v[400001];

muchie sol[400001];

int radacina(int x)
{

    if(t[x]==0) return x;

    t[x]=radacina(t[x]);

    return t[x];

}

void apm()
{

    int i=0;
    selectate=0;
    while(selectate<n-1)
    {
        rx=radacina(v[i].x);
        ry=radacina(v[i].y);

        if(rx!=ry)
        {
            selectate++;
            cost+=v[i].c;
            sol[selectate]=v[i];
            t[rx] = ry;

        }

        i++;

    }
}

bool cmp(muchie a,muchie b){

    return a.c<b.c;

}

int main()
{

    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

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

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

        scanf("%d",&v[i].x);
        scanf("%d",&v[i].y);
        scanf("%d",&v[i].c);


    }

    sort(v+1,v+m+1,cmp);

    apm();

    printf("%d\n",cost);

    printf("%d\n",selectate);

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

        printf("%d %d\n",sol[i].y,sol[i].x);

    }

    return 0;

}