#include <stdio.h>
#define N_MAX 200000
#define M_MAX 400000

typedef struct{
    int vf, next, w;
}graf;
graf adj[ M_MAX + 1 ];
int ult[ N_MAX + 1 ];

char ap[ N_MAX + 1 ];

int edge1[ N_MAX ], edge2[ N_MAX ], val[ N_MAX ];
int ph[ N_MAX ];
int dr;

void intersch ( int x, int y ){
    int aux;
    ph[ edge2[ x ] ] = y;  ph[ edge2[ y ] ] = x;
    aux = val[ x ];  val[ x ] = val[ y ];  val[ y ] = aux;
    aux = edge1[ x ];  edge1[ x ] = edge1[ y ];  edge1[ y ] = aux;
    aux = edge2[ x ];  edge2[ x ] = edge2[ y ];  edge2[ y ] = aux;
    return ;
}

void urcare( int x ){
    int y = x / 2;
    while ( x > 1 && val[ y ] > val[ x ] ){
        intersch ( x, y );
        x = y;
        y = x / 2;
    }
    return ;
}

void coborare ( int x ){
    int poz, a, b, gasit = 1;
    while ( x * 2 < dr && gasit ){
        poz = x;
        gasit = 0;
        a = x * 2;
        b = a + 1;
        if ( val[ a ] < val[ x ] ){
            poz = a;
            gasit = 1;
        }
        if ( b < dr ){
            if ( val[ a ] > val[ b ] ){
                if ( val[ x ] > val[ b ] ){
                    poz = b;
                    gasit = 1;
                }
            }
        }
        intersch ( x, poz );
        x = poz;
    }
    return ;
}

int main()
{
    FILE *in = fopen ( "apm.in", "r" );
    int n, m;
    fscanf ( in, "%d%d", &n, &m );
    int i, g, x, y, k = 1;
    for ( i = 1; i <= m; i++ ){
        fscanf ( in, "%d%d%d" ,&x, &y, &g );

        adj[ k ] . vf = y;
        adj[ k ] . next = ult[ x ];
        adj[ k ] . w = g;
        ult[ x ] = k;
        k++;

        adj[ k ] . vf = x;
        adj[ k ] . next = ult[ y ];
        adj[ k ] . w = g;
        ult[ y ] = k;
        k++;
    }
    fclose ( in );

    int poz = ult[ 1 ], rez = 0;
    dr = 1;
    while ( poz > 0 ){
        edge1[ dr ] = 1;
        edge2[ dr ] = adj[ poz ] . vf;
        val[ dr ] = adj[ poz ] . w;
        ph[ adj[ poz ] . vf ] = dr;

        urcare ( dr );
        dr++;
        coborare ( dr - 1 );
        poz = adj[ poz ] . next;
    }
    ap[ 1 ] = 1;

    for ( i = 1; i < n; i++ ){
        rez += val[ 1 ];
        ap[ edge2[ 1 ] ] = 1;
        dr--;
        intersch ( 1, n - i );
        if ( n - i != dr )   intersch ( dr, 1 );
        coborare ( 1 );

        poz = ult[ edge2[ n - i ] ];
        while ( poz > 0 ){
            if ( !ap[ adj[ poz ] . vf ] ){
                if ( ph[ adj[ poz ] . vf ] != 0 ){
                    if ( adj[ poz ] . w < val[ ph[ adj[ poz ] . vf ] ] ){
                        edge1[ ph[ adj[ poz ] . vf ] ] = edge2[ n - i ];
                        edge2[ ph[ adj[ poz ] . vf ] ] = adj[ poz ] . vf;
                        val[ ph[ adj[ poz ] . vf ] ] = adj[ poz ] . w;

                        urcare ( ph[ adj[ poz ] . vf ] );
                        coborare ( ph[ adj[ poz ] . vf ] );
                    }
                }
                else{
                    edge1[ dr ] = edge2[ n - i ];
                    edge2[ dr ] = adj[ poz ] . vf;
                    val[ dr ] = adj [ poz ] . w;
                    ph[ adj[ poz ] . vf ] = dr;
                    urcare ( dr );
                    dr++;
                }
            }
            poz = adj[ poz ] . next;
        }
    }
    FILE *out = fopen ( "apm.out", "w" );
    fprintf ( out, "%d\n%d\n", rez, n - 1 );
    for ( i = n - 1; i > 0; i-- ){
        fprintf ( out, "%d %d\n", edge1[ i ], edge2[ i ] );
    }
    return 0;
}