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

struct muc{
       int x, y, c;       
};

muc G[DIM];
int t[DIM];
int h[DIM];
vector< pair< int, int> > M;
vector<int> caract;

void Read();
void Kruskall();
void Write();
void Union( int x, int y );
int Find( int x );


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

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

int Compar(muc a, muc b) {
    return a.c < b.c;
}

void Kruskall()
{    
     sort( G+1, G + m +1, Compar );
                       
     for( int i = 1; i <= m; ++i )
     {
          int v1 = Find( G[i].x );
          int v2 = Find( G[i].y );

          if( v1 != v2 )
          {
              k++;
              M[k] = make_pair( G[i].x , G[i].y ); 
              
              cost_min += G[i].c;
              
              Union( v1, v2 );
              /*
              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';
}

void Union( int x, int y )
{
     if( h[x] > h[y] )
         t[y] = x;
     else
     {
         t[x] = y;
         if( h[x] == h[y] ) 
             h[y] += 1;
     }
}

int Find( int x )
{
     if( t[x] != x )
         t[x] = Find( t[x] );
     return t[x];
}