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

 # define dim 200005
 # define inf 999999
 # define pb push_back

 using namespace std;

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

 struct arbore
 {
     int nod, cost;
 };

 struct solutie
 {
     int X, Y;
 };

 vector < arbore > a[ dim ];
 int N, M;
 int start;
 bool viz[ dim ];
 int t[ dim ], s[ dim ];
 int S = 0, cnt = 1;
 solutie sol[ dim ];

 void citire()
 {
     int i, x, y, z;

     f >> N >> M;
     for ( i = 1 ; i <= M ;i ++ )
     {
         f >> x >> y >> z;
         a[ x ].pb( ( arbore ) { y, z } );
         a[ y ].pb( ( arbore ) { x, z } );
     }

     start = 2;
     for ( i = 1 ; i <= N ; i++ )
         s[ i ] = start ;
     viz[ start ] = 1;
     s[ start ] = 0;
 }

 void rezolva()
 {
     int i, j, var, nod, ind ;
     var = nod = inf;

     for ( i = 1 ; i < N ; i++ )
     {
        var = nod = inf;

        for (  j = 1 ; j <= N  ; j++ )
            if( viz[ j ] == 1 )
            {
                for ( ind = 0 ; ind < a[ j ].size() ; ind++ )
                     if ( a[ j ][ ind ].cost < var && viz[ a[ j ][ ind ].nod ] == 0 )
                     {
                         var = a[ j ][ ind ].cost;
                         nod = a[ j ][ ind ].nod;
                         sol[ cnt ].X = j;
                         sol[ cnt ].Y = a[ j ][ ind ].nod;
                     }
            }

        S = S + var;
        viz[ nod ] = 1;
        cnt++;

     }

     g << S << "\n" << N - 1 << "\n";
     for ( i = 1 ; i < cnt ; i++ )
         g << sol[ i ].X << " " << sol[ i ].Y << "\n";
 }

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