#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>



using namespace std;

const int MAX = 400010;

int X[MAX], Y[MAX], C[MAX], CLS [MAX];
vector < int > IND , MUCHII ;



int findParent ( int x ){

    if ( x == CLS [ x ] )
        return x;

    CLS [ x ] = findParent ( CLS [ x ] );

}

void Union ( int x, int y ){

    x = findParent ( x );
    y = findParent ( y );

    CLS [ x ] = y;

   //     CLS [ y ] = x;

}

bool myCmp ( int i , int j){

    return ( C [ i ] < C [ j ] ) ;

}

int main()
{
    int N , M , i = 0 ,cpyM , ANS = 0, SUM = 0;
    ifstream f("apm.in" , ios::in );
    ofstream g("apm.out" , ios::out);
    f>>N>>M;
    cpyM = M ;
    IND.resize ( M + 1) ;

    while (cpyM--){
        i++;
        f>>X [ i ]>> Y [ i ] >> C [ i ];
        IND [ i ] = i;
    }
    for ( i = 1 ; i <= N; i++){
        CLS [ i ] = i;
    }
    sort(IND.begin() + 1 , IND.begin() + M + 1, myCmp );

   for ( i = 1; i <= M ; i++){

        if ( findParent ( X [ IND [ i ] ] ) != findParent ( Y [ IND [ i ] ] ) ) {
            Union ( X [ IND [ i ] ] , Y [ IND [ i ] ] ) ;
            ANS++ ;
            SUM += C  [ IND [ i ] ] ;
            MUCHII.push_back ( IND [ i ] );
        }
   }

  g<<SUM<<"\n"<<ANS;
  for ( i = 0 ; i < MUCHII.size() ; i++)
    g<<"\n"<<X [ MUCHII [ i ] ]<<" "<<Y [ MUCHII [ i ] ];


    g.close();
    f.close();
    return 0;
}