#include <stdio.h>
#include <stdlib.h>

int a[3][400000], sef[200000];
int rez[200000];

int sef_suprem( int x ) {
  if( sef[x] == x )
    return x;
  return sef[x] = sef_suprem( sef[x] );
}

void myqsort( int begin, int end ) {
  int aux, b = begin, e = end,
    pivot = a[2][(begin+end)/2];
  while( a[2][b] < pivot )
    b++;
  while( a[2][e] > pivot )
    e--;
  while( b < e ) {
    aux = a[2][b];
    a[2][b] = a[2][e];
    a[2][e] = aux;
    aux = a[0][b];
    a[0][b] = a[0][e];
    a[0][e] = aux;
    aux = a[1][b];
    a[1][b] = a[1][e];
    a[1][e] = aux;
    do
      b++;
    while( a[2][b] < pivot );
    do
      e--;
    while( a[2][e] > pivot );
  }
  if( begin < e )
    myqsort( begin, e );
  if( e + 1 < end )
    myqsort( e + 1, end );
}

int main() {
    FILE *fin, *fout;
    int n, m, i, nr, cost, sefa, sefb;
    fin = fopen( "apm.in", "r" );
    fscanf( fin, "%d%d", &n, &m );
    for( i = 0; i < m; i++ ) {
      fscanf( fin, "%d%d%d", &a[0][i], &a[1][i], &a[2][i] );
      a[0][i]--;
      a[1][i]--;
    }
    fclose( fin );
    myqsort( 0, m - 1 );
    for( i = 0; i < n; i++ )
      sef[i] = i;
    nr = cost = 0;
    for( i = 0; i < m; i++ ) {
      sefa = sef_suprem( a[0][i] );
      sefb = sef_suprem( a[1][i] );
      if( nr < n - 1 && sefa != sefb ) {
        cost += a[2][i];
        sef[sefb] = sefa;
        rez[nr] = i;
        nr++;
      }
    }
    fout = fopen( "apm.out", "w" );
    fprintf( fout, "%d\n%d\n", cost, nr );
    for( i = 0; i < nr; i++ )
      fprintf( fout, "%d %d\n", a[0][rez[i]] + 1, a[1][rez[i]] + 1 );
    fclose( fout );
    return 0;
}