#include<fstream>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;

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

#define DIM 400001

int n, m, k;
int cost_min;

vector< pair<int, pair<int, int> > > G;
vector< pair< int, int> > M;
vector<int>caract;

void Read();
void Kruskall();
void Write();

int main()
{
    Read();
    Kruskall();
    Write();
    
    fin.close();
    fout.close();
    
    return 0;
}

void Read()
{
     fin >> n >> m;
     caract.resize( n+1 );
     G.resize( m+1 );
     M.resize( n+1 );
     int x, y, c;
     for( int i = 1; i <= m; ++i )
     {
          fin >> x >> y >> c;
          G[i] = make_pair(c, make_pair(y,x) );
     }
}

void Kruskall()
{
     for( int i = 1; i <= n; ++i )
          caract[i] = i;
     
     //sort( G, G + m );
     
     pair<int, pair<int, int> > aux;
     for( int i = 1; i <= m-1; ++i )
          for( int j = i+1; j <= m; ++j )
          {
               if( G[i].first > G[j].first )
               {
                   aux = G[i];
                   G[i] = G[j];
                   G[j] = aux;
               }
               if( G[i].first == G[j].first && G[i].second.first > G[j].second.first  )
               {
                   aux = G[i];
                   G[i] = G[j];
                   G[j] = aux;
               }
               if( G[i].first == G[j].first && G[i].second.first == G[j].second.first && G[i].second.second > G[j].second.second )
               {
                   aux = G[i];
                   G[i] = G[j];
                   G[j] = aux;
               }
          }
                                    
     for( int i = 1; i <= m; ++i )
     {
          int v1 = G[i].second.first;
          int v2 = G[i].second.second;

          if( caract[v1] != caract[v2] )
          {
              k++;
              M[k] = make_pair( G[i].second.first , G[i].second.second ); 
              
              cost_min += G[i].first;
              
              int car = caract[v1];
              for( int j = 1; j <= n; ++j )
              {
                   if( caract[j] == car )
                       caract[j] = caract[v2];
              }
          }
          
          if( k == n - 1 )
              break;
     }
}

void Write()
{
     fout << cost_min << '\n' << k << '\n';
     for( int i = 1; i <= k; ++i )
          fout << M[i].first << ' ' << M[i].second << '\n';
}