#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];
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 );
     M.resize( n+1 );
     int x, y, c;
     for( int i = 1; i <= m; ++i )
     {
          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()
{
     for( int i = 1; i <= n; ++i )
          caract[i] = i;
     
     sort( G+1, G + m +1, Compar );
                       
     for( int i = 1; i <= m; ++i )
     {
          int v1 = G[i].x;
          int v2 = G[i].y;

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