//Algoritmul lui Prim cu HEAP

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("apm.in") ;
ofstream fout ("apm.out") ;

struct nod
{
    nod * next ;
    int info ;
    int cost ;
} ;

int N , M , poz [200001] , cheie [200001] , h [200001] , viz [200001] , parinte [200001] , lg_h ;
nod * L [200001] ;

void Add ( int , int , int ) ;
void Citire ()
{
    int a , b , c ;
    fin >> N >> M ;
    while ( M >= 1 )
    {
        fin >> a >> b >> c ;
        Add ( a , b , c ) ;
        -- M ;
    }
}

void Add ( int a , int b , int c )
{
    nod * p = new nod ;
    p->info = b ;
    p->cost = c ;
    p->next = L[a] ;
    L[a] = p ;

    p = new nod ;
    p->info = a ;
    p->cost = c ;
    p->next = L[b] ;
    L[b] = p ;
}

void swap ( int i , int j )
{
    int aux ;

    aux = h [i] ;
    h [i] = h [j] ;
    h [j] = aux ;

    poz [ h[i] ] = i ;
    poz [ h[j] ] = j ;

}


void upheap ( int fiu )
{
    int tata;
    if ( fiu > 1 )
    {
        tata = fiu / 2 ;
        if ( cheie [ h[tata] ] > cheie [ h[fiu] ] )
        {
            swap (tata, fiu);
            upheap ( tata ) ;
        }
    }
}

void downheap ( int tata )
{
    int fiu;
    if ( tata <= lg_h / 2 )
    {
        if ( 2 * tata + 1 <= lg_h )
             if ( cheie [ h [ 2 * tata ] ] < cheie [ h [ 2 * tata + 1 ] ] )
                         fiu = 2 * tata ;
             else
                         fiu = 2 * tata + 1 ;
        else
             fiu = 2 * tata ;
        if ( cheie [ h [ tata ] ] > cheie [ h [ fiu ] ] )
                  swap ( tata , fiu ) , downheap ( fiu ) ;

    }
}

void InsertHeap ( int x )
{
    h [ ++ lg_h ] = x ;
    poz [ x ] = lg_h ;
    upheap ( lg_h );
}

void PopHeap ()
{
        swap ( 1 , lg_h );
        -- lg_h ;
        downheap (1) ;
}

#define inf 20000000

void APCM ( int radacina )
{
    int i , cst = 0 ;
    for ( i = 1 ; i <= N ; ++ i )
           cheie [i] = inf ;

    cheie [ radacina ] = 0 ;
    // parinte [ radacina ] = 0 ;

    InsertHeap ( radacina ) ;

    while ( lg_h != 0 )
    {
        radacina = h [1] ;
        viz [ radacina ] = 1;
        PopHeap () ;
        cst += cheie [ radacina ] ;
        for ( nod * p = L [ radacina ] ; p != 0 ; p = p->next )
             if ( viz [ p->info ] == 0 && p->cost < cheie [ p->info ] )
                {
                   cheie [ p->info ] = p->cost ;
                   parinte [ p->info ] = radacina ;

                   if ( poz [ p->info ] == 0 )
                          InsertHeap ( p->info )  ;
                   else
                          upheap ( poz [ p->info ] ) ;
                }

    }

    fout << cst << "\n" ;
    fout << N - 1 << "\n" ;

    for ( i = 2 ; i <= N ; ++ i )
          fout << parinte [i] << " " << i << "\n" ;

}
int main()
{
    Citire();
    APCM (1) ;
    return 0;
}