#include <cstdio>
#include <algorithm>
using namespace std;

#define Nmax 200002
#define Mmax 400002

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

struct muchie{
    int x, y, c;
}v[Mmax];

int tata[Nmax], rang[Nmax], ind[Nmax];

bool cmp ( muchie A, muchie B ){
    return A.c < B.c;
}

int Find ( int x ){
    int rad, aux;

    for ( rad = x; rad != tata[rad]; rad = tata[rad] );

    while ( x != tata[x] ){
        aux = tata[x];
        tata[x] = rad;
        x = aux;
    }
    return rad;
}

void Unite ( int a, int b ){
    if ( rang[a] > rang[b] )
        tata[b] = a;
    else
        tata[a] = b;

    if ( rang[a] == rang[b] )
        rang[b]++;
}

int main(){

    int N, M;

    fscanf ( f, "%d%d", &N, &M );

    for ( int i = 1; i <= N; ++i ){
        tata[i] = i;
        rang[i] = 1;
    }

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

    sort ( v + 1, v + M + 1, cmp );

    int cost = 0;

    for ( int i = 1; i <= M; ++i ){
        int a = Find ( v[i].x );
        int b = Find ( v[i].y );

        if ( a != b ){
            cost += v[i].c;
            Unite ( a, b );
            ind[++ind[0]] = i;
        }
    }

    fprintf ( g, "%d\n%d\n", cost, N - 1 );

    for ( int i = 1; i < N; ++i )
        fprintf ( g, "%d %d\n", v[ind[i]].x, v[ind[i]].y );

    return 0;
}