#include <fstream>
#include <algorithm>

#include <vector>
#include <cstring>

#define NMAX 200005
#define get_max(a,b) ((a)>(b)?(a):(b))
#define get_min(a,b) ((a)<(b)?(a):(b))

using namespace std;

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

int N , M ;

struct APM {

  int a , b, c;
}Arb[ 2*NMAX ];

int TT[NMAX];
int Answer , nr_nodes ;

pair < int , int  > Sol[NMAX];


bool cmp ( APM A , APM B ){
   return A.c  < B.c;
}

int Find ( int X ){
   int i , j ;
   i = TT[X];
   for(;i!=TT[i];i = TT[i]);
  //   for(; X!=i; j = TT[X] , TT[X] = i , X  = j )
   return i;
}
void Unite ( int A , int B ){
  TT[A] = B;
  return ;
}


void DoAPM ( void  ){
    int i , j  ;
    for ( int i = 1 ; i <=  N ; ++i )
    TT[i]  = i ;
    for ( int i = 1 ; i <= M  ; ++i ){
       int findFatherA = Find( Arb[i].a );
       int findFatherB = Find( Arb[i].b );

      if ( findFatherA != findFatherB )
       {
          Answer += Arb[i].c;
          Unite( findFatherA , findFatherB );
          Sol[ ++nr_nodes ].first = Arb[i].a;
          Sol[ nr_nodes ].second = Arb[i].b;
       }


    }

}


int main ( void ){

  int  i , j ;
  in >> N >> M ;
  for ( i = 1 ; i <= M ; ++i )
     in >> Arb[i].a >> Arb[i].b >> Arb[i].c;
  sort ( Arb + 1 , Arb + M + 1 , cmp );
  DoAPM();
  out << Answer << "\n" << nr_nodes << "\n";
  for ( i = 1 ; i < N ; ++i )
  out << Sol[i].first << " " << Sol[i].second << "\n";
  return 0 ;
}