// Kruskal eficient
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std ;

ifstream f ("apm.in") ;
ofstream g ("apm.out") ;

struct muchie {
int i , j , c ;
    };
muchie V[400002] ;
int n , m , gr[200002] , cmin ;
vector < pair < int , int > > Memo ;

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

int grupa(int i)
{
    if ( gr[i] == i) return i;
    gr[i] = grupa( gr[i] ) ;
    return gr[i];
}
void reuneste ( int i , int j )
{
 gr[grupa(i)] = grupa (j) ;
}

int main ()
{
 f >> n >> m ;
 for ( int cnt = 1 ; cnt <= m ; ++cnt )
     f >> V[cnt].i >> V[cnt].j >> V[cnt].c ;
 for ( int cnt = 1 ; cnt <= n ; ++cnt )
    gr[cnt] = cnt ;
 sort ( V + 1 , V + m + 1 , comp ) ;
 for ( int cnt = 1 ; cnt <= m ; ++cnt )
    {
     if ( grupa ( V[cnt].i ) != grupa ( V[cnt].j ) )
        {
         cmin += V[cnt].c ;
         reuneste ( V[cnt].i , V[cnt].j ) ;
         Memo.push_back( make_pair ( V[cnt].i , V[cnt].j ) ) ;
        }
    }
 g << cmin << "\n" << n - 1 <<  "\n" ;
 for ( vector < pair < int , int > > :: iterator I = Memo.begin () ; I < Memo.end () ; ++I )
    g << I -> first << " " << I -> second << "\n" ;

}