#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(x,y) );
     }
}

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;
               }
                   
     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;
              
              for( int i = 1; i <= n; ++i )
                   if( caract[i] == v1 )
                       caract[i] = v2;
          }
          
          if( k == n - 1 )
              break;
     }
}

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