# include <fstream>
 # include <cstring>
 # include <algorithm>
 # include <vector>

 # define dim1 400005
 # define dim2 200005

 using namespace std;

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

 struct arbore
 {
     int X, Y, C;
 };

 arbore A[ dim1 ], sol[ dim1 ];
 int nod[ dim2 ];
 int lg_sol, minim;
 int N, M;

 inline bool cmp( arbore a, arbore b )
 {
     return a.C < b.C;
 }
 void citire()
 {
     int i;
     f >> N >> M;
     for ( i = 1 ; i <= M ; i++ )
         f >> A[ i ].X >> A[ i ].Y >> A[ i ].C;

 }
 void conex()
 {
     int i;
     for ( i = 1 ; i <= N ; ++i )
        nod[ i ] = i;
 }

 inline int cauta( int X )
 {
     int r = X;
     while ( r != nod[ r ] )
        r = nod[ r ];
     return r;

 }

 void leaga( int X, int Y )
 {
     nod[ X ] = Y;
 }

 void rezolva()
 {
     int i, X, Y;

     sort( A + 1, A + M + 1, cmp );

     for ( i = 1 ; i <= M && lg_sol < N ; i++ )
     {
         X = cauta( A[ i ].X );
         Y = cauta( A[ i ].Y );

         if ( X != Y )
         {
             leaga( X, Y );
             lg_sol++;
             sol[ lg_sol ].X = A[ i ].X;
             sol[ lg_sol ].Y = A[ i ].Y;
             minim += A[ i ].C;
         }
     }

     g << minim << "\n";
     g << lg_sol << "\n";
     for ( i = 1 ; i <= lg_sol ; i++ )
        g << sol[ i ].X << " " << sol[ i ].Y << "\n";
 }

 int main()
 {
     citire();
     conex();
     rezolva();
     return 0;
 }