#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  ;

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]);
   return i;
}
void Unite ( int A , int B ){
  TT[A] = B;
  return ;
}


void DoAPM ( void  ){
    int i , j , nr_nodes = 0 ;
    for ( int i = 1 ; i <= M and nr_nodes < N ; ++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" << N-1 << "\n";
  for ( i = 1 ; i < N ; ++i )
  out << Arb[i].a << " " << Arb[i].b << "\n";
  return 0 ;
}