// Algoritmul lui Kruskal cu multimi disjuncte // COMPL : O ( M log *N + M log M ) // eficient cand numarul de muchii e mic
// log *N == inversa functiei lui Ackerman ..poate fi aproximata cu O (1) ;
// Algoritmul lui Prim este eficient atunci cand graful este dens ( numarul de muchii M  este de ordinul O (N^2) // COMPL : O ( M log N )
#include <iostream>
#include <fstream>
#include <vector >
#include <algorithm>

using namespace std;

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

struct muchie
{
    int x ;
    int y ;
    int cost ;

} ;

int N , M ;
vector <muchie> L ;

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 )
{
    muchie * aux = new muchie ;
    aux->x = a ;
    aux->y = b ;
    aux->cost = c ;
    L.push_back ( *aux ) ;
}

bool cmp ( muchie i  , muchie j )
{
    return ( i.cost < j.cost ) ;
}

int P [200001] , R [200001] ;

int find ( int x )
{
    int root ;
    for ( root = x ; root != P [root] ; root = P [root] ) ;

    int aux ;

    while ( x != P [x] )
    {
           aux = P [x] ;
           P [x] = root ;
           x = aux ;
    }

    return root ;
}

void Union ( int i , int j )
{
    if ( R [i] > R[j] )
            P [j] = i;
    else
            P [i] = j ;

    if ( R [i] == R [j] )
            ++ R [j] ;
}

void Kruskal ()
{
    vector <muchie> krusk ;
    for ( int i = 1 ; i <= N ; ++ i )
           P [i] = i , R [i] = 1 ;

    sort ( L.begin() , L.end() , cmp ) ;

    int A , B , cst = 0 ;

    for ( unsigned int i = 0 ; i < L.size() ; ++ i )

         if ( ( A = find ( L [i].x ) ) != ( B = find ( L [i].y ) ) )

            cst += L [i].cost , krusk.push_back( L [i] ) , Union ( A ,B ) ;

    fout << cst << " \n " ;
    fout << N - 1 << " \n " ;
    for ( unsigned int i = 0 ; i < krusk.size() ; ++ i )
          fout << krusk [i].x << " " << krusk [i].y << " \n " ;
}

int main()
{
    Citire () ;
    Kruskal() ;
    return 0;
}