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

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

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

int n, m;
int t[200010];
int h[200010];
int cost_min;

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

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

void Read()
{
     fin >> n >> m;
     
     int a, b, c;
     
     for(int i = 1; i <= m; ++i )
     {
          if( i < n )
              t[i] = i;
              
          fin >> a >> b >> c;
          G.push_back( make_pair( c, make_pair( a, b ) ) ); 
     }
     t[n] = n;
}

void Solve()
{
     sort( G.begin(), G.end() );
     int k = 0;
     for( int i = 0; i < G.size(); ++i )
     {
          int v1 = Find( G[i].second.first );
          int v2 = Find( G[i].second.second );
          if( v1 != v2 )
          {
              k++;
              Union(v1, v2);
              M.push_back( make_pair(G[i].second.first, G[i].second.second) );
              cost_min += G[i].first;
          }
          if( k == n-1 )
              return;
     }
}

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

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]++;
     }
}

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