#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int MAXN = 200005;

int M[MAXN];

vector<pair<int, pair<int, int>>> edges;
vector<pair<int, int>> sol;

int root( int u ) {
  if ( M[u] == u ) {
    return u;
  }
  return M[u] = root(M[u]);
}

void join( int u, int v ) {
  M[root(u)] = root(v);
}

int main() {
  int n, m, u, v, c, res = 0;

  fin >> n >> m;
  for ( int i = 1; i <= n; ++i ) M[i] = i;
  for ( int i = 0; i < m; ++i ) {
    fin >> u >> v >> c;
    edges.push_back( {c, {u, v}} );
  }
  sort( edges.begin(), edges.end() );
  for ( int i = 0; i < m; ++i ) {
    if ( root(edges[i].second.first) != root(edges[i].second.second) ) {
      sol.push_back({edges[i].second.first, edges[i].second.second});
      res += edges[i].first;
      join( edges[i].second.first, edges[i].second.second );
    }
  }
  fout << res << "\n" << sol.size() << "\n";
  for ( int i = 0; i < sol.size(); ++i ) {
    fout << sol[i].first << " " << sol[i].second << "\n";
  }
  fin.close();
  fout.close();
  return 0;
}