#include <cstdio>
#include <vector>
#define NMAX 200000
#define MMAX 400000
#define INF 1001
#define NIL -1
#define SEEN -2
FILE *fin, *fout;
using namespace std;
vector < pair <int, int> > G[NMAX];

int heap[NMAX], nr,
    unde[NMAX], tata[NMAX], cost[NMAX],
    Weight;

//heap[i] = indicele nodului cu costul respectiv aseazarii in heap
//unde[i] = pe ce pozitie e nodul i in heap
//cost[i] = costul muchiei minime incidete spre i
//indexam totul de la 0

void up( int poz ) {
  int tata = ( poz - 1 ) >> 1;
  while ( poz != 0 && cost[heap[tata]] > cost[heap[poz]] ) {
    swap( unde[heap[tata]], unde[heap[poz]] );
    swap( heap[tata], heap[poz] );
    poz = tata;
    tata = ( poz - 1 ) >> 1;
  }
}

void push( int nod ) {
  heap[nr] = nod;
  unde[nod] = nr;
  nr++;
  up( nr - 1 );
}

void down( int poz ) {
  int fiu = ( poz << 1 ) + 1;
  bool ok = true;
  while ( fiu < nr && ok ) {
    ok = false;
    if ( fiu + 1 < nr && cost[heap[fiu]] > cost[heap[fiu + 1]] )
      fiu++;
    if ( cost[heap[poz]] > cost[heap[fiu]] ) {
      swap( unde[heap[poz]], unde[heap[fiu]] );
      swap( heap[poz], heap[fiu] );
      poz = fiu;
      fiu = ( poz << 1 ) + 1;
      ok = true;
    }
  }
}

void pop() {
  unde[heap[nr - 1]] = 0;
  unde[heap[0]] = SEEN;
  swap( heap[0], heap[nr - 1] );
  nr--;
  down( 0 );
}

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 );
  while ( m-- ) {
    fscanf( fin, "%d%d%d", &x, &y, &c );
    x--; y--;
    G[x].push_back( make_pair( y, c ) );
    G[y].push_back( make_pair( x, c ) );
  }
  for ( i = 0; i < n; i++ ) {
    unde[i] = NIL;
    tata[i] = NIL;
    cost[i] = INF;
  }
  cost[0] = 0;
  push( 0 );
  int varf;
  for ( i = 0; i < n; i++ ) {
    varf = heap[0];
    pop();
    Weight += cost[varf];
    for ( x = 0; x < G[varf].size(); x++ ) {
      y = G[varf][x].first;
      c = G[varf][x].second;
      if ( unde[y] != SEEN && cost[y] > c ) {
        cost[y] = c;
        tata[y] = varf;
        if ( unde[y] == NIL )
          push( y );
        else
          up( unde[y] );
      }
    }
  }
  fprintf( fout, "%d\n%d\n", Weight, n - 1 );
  for ( i = 1; i < n; i++ )
    fprintf( fout, "%d %d\n", tata[i] + 1, i + 1 );
  fclose( fin );
  fclose( fout );
    return 0;
}