#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(const void *a, const 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,j;
    muchie aux;
    fscanf(f,"%d", &n);
    fscanf(f,"%d", &m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d\n", &graf[i].n1, &graf[i].n2, &graf[i].cost);
    }


    for(i=1;i<=m;i++)
    {
        for(j=i+1;j<=m;j++)
        {
            if(graf[i].cost>graf[j].cost)
            {
                aux = graf[j];
                graf[j] = graf[i];
                graf[i] = aux;
            }
        }
    }
    for(i=1;i<=m;i++)
    {
        printf("%d %d %d\n", graf[i].n1, graf[i].n2, graf[i].cost);
    }

    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;
}