#include <stdio.h>
#include <vector>
#include <algorithm>

struct DSU {
  std::vector<int> dsu;
  DSU( int n ): dsu(n, -1) {}
  int find( int u ){
    if( dsu[u] < 0 ) return u;
    return dsu[u] = find( dsu[u] );
  }

  bool unite( int a, int b ) {
    a = find( a ); b = find( b );
    if( a == b ) return false;

    if( -dsu[a] > -dsu[b] ){
      dsu[a] += dsu[b];
      dsu[b] = a;
    }else{
      dsu[b] += dsu[a];
      dsu[a] = b;
    }
    return true;
  }
};

int main() {
  FILE *fin = fopen( "apm.in", "r" );
  FILE *fout = fopen( "apm.out", "w" );

  int n, m;
  fscanf( fin, "%d%d", &n, &m );

  struct Edge { int cost, a, b; };
  std::vector<Edge> edges;
  for( int i = 0; i < m; i++ ){
    int a, b, cost;
    fscanf( fin, "%d%d%d", &a, &b, &cost );
    edges.push_back({ cost, --a, --b });
  }

  std::sort( edges.begin(), edges.end(), []( const Edge &a, const Edge &b ) -> bool {
    return a.cost < b.cost;
  } );

  DSU dsu(n);
  int total = 0;
  std::vector<std::pair<int, int>> out;
  for( Edge e : edges )
    if( dsu.unite( e.a, e.b ) ){
      total += e.cost;
      out.emplace_back( e.a, e.b );
    }

  fprintf( fout, "%d\n", total );
  fprintf( fout, "%d\n", (int)out.size() );
  for( auto [a, b]: out )
    fprintf( fout, "%d %d\n", a + 1, b + 1 );

  fclose( fin );
  fclose( fout );
  return 0;
}