#include <stdio.h>
#include <algorithm>
#define N 200005
#define M 400005

struct muchie
{
    int x,y,cost;
};
bool cmp(muchie a,muchie b)
{
    return a.cost<b.cost;
}

int n,m,i,k,cost_total,x,y,c,q;
int t[N];
muchie muchii[M],arb[N];

int tata(int x)
{
    if(t[x]==0)
        return x;
    t[x]=tata(t[x]);
    return t[x];
}
void unire(int n1,int n2)
{
    t[tata(n1)]=tata(n2);
}
int main()
{
    FILE *f1,*f2;
    f1=fopen("apm.in","r");
    f2=fopen("apm.out","w");

    fscanf(f1,"%d%d",&n,&m);
    for(i=0;i<m;i++)
        fscanf(f1,"%d%d%d",&muchii[i].x,&muchii[i].y,&muchii[i].cost);

    std::sort(muchii,muchii+m,cmp);

    for(i=0,k=1;i<m && k<n;i++)
    {
        x=muchii[i].x;
        y=muchii[i].y;
        c=muchii[i].cost;
        if(tata(x)!=tata(y))
        {
            unire(x,y);
            cost_total+=c;
            arb[k++]=muchii[i];

        }
    }

    fprintf(f2,"%d\n%d\n",cost_total,n-1);
    for(i=1;i<n;i++)
        fprintf(f2,"%d %d\n",arb[i].x,arb[i].y);


    return 0;
}