#include <fstream>
#define MAXN 200000
using namespace std;

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

struct mc{
  int x, y, cost;
}muchii[MAXN*2 + 1];

struct solutie{
  int x,y;
}sol[MAXN + 1];

int sef[MAXN + 1];

int find( int i ) {
  if ( sef[i] == i )
    return i;
  return sef[i] = find( sef[i] );
}

void myqsort( int begin, int end ) { //sortam muchiile dupa cost
  int aux, b = begin, e = end,
    pivot = muchii[(begin + end) / 2].cost;
  while (muchii[b].cost < pivot)
    b++;

  while (muchii[e].cost > pivot)
    e--;

  while( b < e ) {
    aux = muchii[b].cost;
    muchii[b].cost = muchii[e].cost;
    muchii[e].cost = aux;
    aux = muchii[b].x;
    muchii[b].x = muchii[e].x;
    muchii[e].x = aux;
    aux = muchii[b].y;
    muchii[b].y = muchii[e].y;
    muchii[e].y = aux;

    do
      b++;
    while (muchii[b].cost < pivot);

    do
      e--;
    while (muchii[e].cost > pivot);
  }

  if ( begin < e )
    myqsort(begin, e);

  if ( e + 1 < end )
    myqsort(e + 1, end);
}

int main(){
  int n, m, i, k, x, y, sefx, sefy, sum;
  fin >> n >> m;
  for( i = 1; i <= m; i++ )
    fin >> muchii[i].x >> muchii[i].y >> muchii[i].cost;
  for( i = 1; i <= n; i++ )
    sef[i] = i;
  myqsort( 1, m );
  k = 1; //prima poz din sol neocupata
  i = 1;
  sum = 0;
  while( k < n ){
    x = muchii[i].x, y = muchii[i].y;
    sefx = find(x);
    sefy = find(y);
    if( sefx != sefy ){ //din multimi diferite
      sef[sefy] = sefx;
      sol[k].x = x, sol[k].y = y;
      k++;
      sum += muchii[i].cost;
    }
    i++;
  }

  fout << sum << '\n' << n - 1 << '\n';
  for( i = 1; i <= n - 1; i++ )
    fout << sol[i].x << ' ' << sol[i].y << '\n';
  return 0;
}