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

typedef struct muchie
{
    int x;
    int y;
    int c;
}MUCHIE;

MUCHIE *g;
MUCHIE *sol;
int *marc;
int n,m;
int cmin;

void citire()
{
    int i;
    FILE *f = fopen("apm.in","r");

    fscanf(f,"%d%d",&n,&m);

    g = (MUCHIE*)malloc((m+1)*sizeof(MUCHIE));
    sol = (MUCHIE*)malloc(n*sizeof(MUCHIE));
    marc = (int *)malloc((n+1)*sizeof(int));


    for(i=1;i<=m;i++)
        fscanf(f,"%d%d%d",&g[i].x,&g[i].y,&g[i].c);

    fclose(f);
}

int pred(const void *a,const void *b)
{
    return ((*(MUCHIE*)a).c - (*(MUCHIE*)b).c);
}

void Kruskal()
{
    int i,j,k;
    int aux;

    for(i=1;i<=n;i++)
        marc[i]=i;

    for(i=1,j=1;i<n;i++)
    {
        while(marc[g[j].x] == marc[g[j].y])
            j++;

        cmin+=g[j].c;
        sol[i]=g[j];

        aux=marc[g[j].y];
        for(k=1;k<n;k++)
            if(marc[k]==aux)
                marc[k]=marc[g[j].x];
        j++;
    }
}

void afisare()
{
    int i;
    FILE *b = fopen("apm.out","w");

    fprintf(b,"%d\n%d\n",cmin,n-1);
    for(i=1;i<n;i++)
        fprintf(b,"%d %d\n",sol[i].x,sol[i].y);

    fclose(b);
}

int main()
{
    citire();

    qsort(g+1,m,sizeof(MUCHIE),pred);

    Kruskal();

    afisare();

    free(g);
    free(marc);
    free(sol);

    return 0;
}