#include <stdlib.h>
#include <stdio.h>

typedef struct muchie{
    int n1,n2,cost;
}muchie;

struct muchie graf[400008], apm[200008];
int t[200008], h[200008];

int cmp(void *a, void *b)
{
    return(((muchie *)a)->cost < ((muchie *)b)->cost);
}

int root(int x)
{
    while (t[x]!=0)
        x = t[x];
    return x;
}

int main()
{
    FILE *f,*g;
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");

    int n=0,m=0,i;
    fscanf(f,"%d", &n);
    fscanf(f,"%d", &m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d", &graf[i].n1, &graf[i].n2, &graf[i].cost);
    }

    qsort(graf,m,sizeof(muchie),cmp);

    int c[200000];
    for(i=1;i<=n;i++)
    {
        c[i]=i;
    }

    int ct=0, cost=0;;

    for(i=1;i<=m;i++)
    {
        int x=graf[i].n1;
        int y=graf[i].n2;
        int rx = root(x);
        int ry = root(y);
        if(rx!=ry){
            ct++;
            apm[ct]=graf[i];
            cost+=graf[i].cost;
            if (h[rx] > h[ry])
                t[ry] = rx;
            else
                if (h[rx] < h[ry])
                    t[rx] = ry;
                else
                {
                    t[ry] = rx;
                    h[rx]++;
                }
        }
        if(ct==n-1){
            break;
        }
    }
    fclose(f);
    fprintf(g,"%d\n%d\n",cost, n-1);
    for(i=1;i<=ct;i++)
        fprintf(g,"%d %d\n", apm[i].n1, apm[i].n2);
    fclose(g);
    return 0;
}