#include <cstdio>
#include <cstdlib>
#include <vector>

#define nmax 50001

using namespace std ;

struct nod
{
    int nod ;
    int distanta ;
}arb[ 3 * nmax ] , asd , infinit;

vector <int> componenta ;
vector <nod> vecini [ nmax ] ;
int N , M ;
int distanta [ nmax ] , poz [ nmax ] ;
int T [ nmax ] ;
int p , u ;
bool valid [ nmax ] ;


nod minim ( nod a , nod b )
{
    if ( a.distanta < b.distanta ) return a;
        else return b;
}
void update ( int nod0 , int stanga , int dreapta , int a , nod b )
{
    if ( stanga == dreapta )
        arb [ nod0 ] = b ;
        else
        {
            int mid = ( stanga + dreapta  ) / 2 ;
            if ( a <= mid ) update ( 2 * nod0 , stanga , mid , a , b ) ;
                else update ( 2 * nod0 + 1 , mid + 1 , dreapta , a , b ) ;
            arb[ nod0 ] = minim ( arb [ 2 * nod0 ] , arb [ 2 * nod0 + 1 ] ) ;
        }
}

void prim ( int nod )
{
    if ( !valid [ nod ] ) return ;
    valid [ nod ] = 0 ;
    //componente.push_back ( nod ) ;
    update ( 1 , 1 , N , nod , infinit ) ;


    for ( int i = 0 ; i < vecini [ nod ].size () ; i++ )
    {
        int vecin = vecini [ nod ][ i ].nod ;
        int muchie = vecini [ nod ][ i ].distanta ;
        int distanta_veche = distanta [ vecin ] ;
        if ( !valid [ vecin ] ) continue ;
        if ( distanta_veche > muchie  )
            {
                distanta [ vecin ] = muchie ;
                T [ vecin ] = nod ;
                asd.nod = vecin ;
                asd.distanta = distanta [ vecin ] ;
                update ( 1 , 1 , N , vecin , asd ) ;
            }

    }
    nod = arb [ 1 ].nod ;
    componenta.push_back ( nod ) ;
    prim ( nod ) ;

}
void build ( int nod , int stanga
             , int dreapta )
{
    if ( stanga == dreapta )
        arb [ nod ] = infinit ;
        else
            {
                int mid = ( stanga + dreapta ) / 2 ;
                build ( 2 * nod , stanga , mid ) ;
                build ( 2 * nod + 1 , mid + 1 , dreapta ) ;
                arb [ nod ] = minim ( arb [ 2 * nod ] , arb [ 2 * nod + 1 ] ) ;
            }
}
void dist ()
{
    valid [ 1 ] = 1 ;
    distanta [ 1 ] = 0;

    for ( int i = 2 ; i <= N + 4 ; i++ )
    {
        valid [ i ] = 1 ;
        distanta [ i ] = infinit.distanta ;
    }
}

int main ()
{
    FILE *fin , *fout ;
    fin = fopen ( "apm.in" , "rt" ) ;
    fout = fopen ( "apm.out" , "wt" ) ;

    fscanf ( fin , "%d %d" , &N , &M ) ;
    for ( int i = 1 ; i <= M ; i++ )
    {
        int a ;
        nod asd ;
        fscanf ( fin , "%d %d %d" , &a , &asd.nod , &asd.distanta ) ;
        vecini [ a ].push_back ( asd ) ;
    }

    infinit.distanta = 1 << 30 ;
    infinit.nod = 0 ;

    dist () ;
    build ( 1 , 1 , N ) ;
    arb [ 1 ].nod = 1 ;
    arb [ 1 ].distanta = infinit.distanta ;
    prim ( 1 ) ;
    int s = 0 ;
    for ( int i = 2 ; i <= N ; i++ )
        if ( distanta [ i ] != infinit.distanta )
            {
                //fprintf ( fout , "%d " , distanta [ i ] ) ;
                s += distanta [ i ] ;
            }
            //else fprintf ( fout , "0 " );

    fprintf ( fout , "%d\n" , s ) ;

    for ( int i = 0 ; i < componenta.size ()  ; i++ )
    {
        int a = componenta [ i ] ;
        fprintf ( fout , "%d %d\n" , T [ a ] , a ) ;
    }


    fclose ( fin ) ;
    fclose ( fout ) ;

    return 0 ;


}