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

typedef struct muchie
{
    int x; //varf initial
    int y; //varf final
    int c; // cost
}MUCHIE;

MUCHIE *g; //graful
int *marc;
MUCHIE *sol; //tin muchiile solutie
int n,m;
int cmin; //cost minim

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]; // schimb tot timpul marcajul lui 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();

    return 0;
}