#include <cstdio>
#include <algorithm>

FILE* in=fopen("apm.in","r");
FILE* out=fopen("apm.out","w");

const int Q=200005,W=400005;

struct mc
{
    int a,b,c;
} v[W];

int n,m;

int rad[Q],lv[Q];

int rez,reza[Q],rezb[Q],r;

void uneste(int p, int q)
{
    rad[rad[q]]=rad[p];
}

int radacina(int p)
{
    if(p!=rad[p])
    {
        rad[p]=radacina(rad[p]);
    }
    return rad[p];
}

bool cmp(const mc &x,const mc &y)
{
    return x.c<y.c;
}

int main()
{
    fscanf(in,"%d%d",&n,&m);

    int a,b,c;

    for(int i=1; i<=m; i++)
    {
        fscanf(in,"%d%d%d",&v[i].a,&v[i].b,&v[i].c);
    }

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

    for(int i=1; i<=n; i++)
    {
        rad[i]=i;
        lv[i]=1;
    }

    for(int i=1; i<=m; i++)
    {
        if( radacina(v[i].a)!=radacina(v[i].b) )
        {
            uneste(v[i].a,v[i].b);

            r++;
            reza[r]=v[i].a;
            rezb[r]=v[i].b;
            rez+=v[i].c;
        }
    }

    fprintf(out,"%d\n%d\n",rez,r);

    for(int i=1; i<=r; i++)
        fprintf(out,"%d %d\n",reza[i],rezb[i]);

    return 0;
}