#include <stdio.h>
#include <stdlib.h>
#define NMAX 200000
#define MMAX 400000
FILE *fin, *fout;
typedef struct {
  int x, y, c;
} muchie;
muchie E[MMAX];
int tata[NMAX], rang[NMAX],
    afis[MMAX], Weight;

int comp( int nod ) {
  int R = nod, aux;
  while ( tata[R] != R )
    R = tata[R];
  while ( nod != R ) {
    aux = tata[nod];
    tata[nod] = R;
    nod = aux;
  }
  return R;
}

void uneste( int x, int y ) {
  int rx = comp( x ), ry = comp( y );
  if ( rang[rx] > ry )
    tata[ry] = rx;
  else
    tata[rx] = ry;
  if ( rang[rx] = rang[ry] )
    rang[ry]++;
}

int pivotare( int st, int dr ) {
  muchie pivot = E[st];
  while ( st < dr ) {
    while ( st < dr && pivot.c <= E[dr].c )
      dr--;
    E[st] = E[dr];
    while ( st < dr && E[st].c <= pivot.c )
      st++;
    E[dr] = E[st];
  }
  E[st] = pivot;
  return st;
}

void quicksort( int inf, int sup ) {
  int poz = pivotare( inf, sup );
  if ( poz - 1 > inf )
    quicksort( inf, poz - 1  );
  if ( poz + 1 < sup )
    quicksort( poz + 1, sup );
}



int main() {
  fin = fopen( "apm.in", "r" );
  fout = fopen( "apm.out", "w" );
  int n, m, i, x, y, c;
  fscanf( fin, "%d%d", &n, &m );
  for ( i = 0; i < m; i++ ) {
    fscanf( fin, "%d%d%d", &E[i].x, &E[i].y, &E[i].c );
    E[i].x--; E[i].y--;
  }
  quicksort( 0, m - 1 );
  for ( i = 0; i < n; i++ ) {
    tata[i] = i;
    rang[i] = 1;
  }
  int nrmucsel = 0;//numarul de muchii selectate
  i = 0;
  while ( nrmucsel < n - 1 ) {
    if ( comp( E[i].x ) != comp( E[i].y ) ) {
      afis[nrmucsel++] = i;//afisam muchia i
      Weight += E[i].c;
      uneste( E[i].x, E[i].y );
    }
    i++;
  }
  fprintf( fout, "%d\n%d\n", Weight, nrmucsel );
  for ( i = 0; i < nrmucsel; i++ )
    fprintf( fout, "%d %d\n", E[afis[i]].x + 1, E[afis[i]].y + 1 );
  fclose( fin );
  fclose( fout );
    return 0;
}