#include <stdio.h>
#include <stdlib.h>
#define MaxM 400001
#define MaxN 200001

struct muchie
{
    int x,y,cost;
};
typedef struct muchie muchie;

int N,R,M,I[MaxM],G[MaxN],V[MaxM];
muchie Me[MaxM];

int grupa( int i )
{
    if( G[i] == i )
        return i;
    G[i] = grupa(G[i]);
    return G[i];
}

void reuniune( int i, int j )
{
    G[grupa(i)] = grupa(j);
}

int comparare( const void * a, const void *b )
{
    muchie *a1 = (muchie*)a;
    muchie *b1 = (muchie*)b;
    return (a1->cost - b1->cost);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    int i,j=-1;
    R = 0;
    scanf("%d %d\n",&N,&M);
    for( i = 0 ; i < M ; ++i )
    {
        scanf("%d %d %d\n",&Me[i].x,&Me[i].y,&Me[i].cost);
        I[i] = i;
    }
    for( i = 1 ; i <= N ; ++i )
        G[i] = i;
    qsort(Me,M,sizeof(struct muchie),comparare);
    /*for( i = 0 ; i < M ; ++i )
        printf("%d %d %d\n",Me[i].x,Me[i].y,Me[i].cost);*/
    for( i = 0 ; i < M ; ++i )
    {
        if( grupa(Me[i].x) != grupa(Me[i].y) )
        {
            R += Me[i].cost;
            reuniune(Me[i].x,Me[i].y);
            V[j++] = i;
        }
    }
    printf("%d\n%d\n",R,N-1);
    for( i = 0 ; i < N-1 ; ++i )
        printf("%d %d\n",Me[ V[i] ].x,Me[ V[i] ].y );
    fclose(stdin);
    fclose(stdout);
    return 0;
}