#include <stdio.h>
#include <vector>
#include <algorithm>
#include <assert.h>
#define nmax 200000

using namespace std;

struct nod{
  int cost;
  int nod1;
  int nod2;
};

vector < pair < int, int > > v[nmax]; ///v[i]->first = vecinii nodului i; v[i]->second = costul muchiei
vector < pair < int, int > > apm;     ///solutia
vector < nod > aux;                      ///derminam muchia ce trb adaugata conf algoritmului prim
char verif[nmax];                  ///verif[i] = daca am adaugat nodul i in apm
int cost_apm, n;

class compare {
  public:
    bool operator () ( nod a, nod b ) const {
      return a.cost > b.cost;
    }
};

void prim( int nod_curent ) {
  nod muchie;
  make_heap( aux.begin(), aux.end(), compare() );
  ///incepem cu nodul 1
  while( nod_curent != -1 ) {
    verif[ nod_curent ] = 1;
    for ( int i = 0; i < v[nod_curent].size(); i++ ) {   ///adaugam muchile vecinilor nodului curent
      if ( verif[ v[nod_curent][i].first ] == 0 ){                 ///daca nu am adaugat inca aceasta muchie
        muchie.cost = v[nod_curent][i].second;
        muchie.nod1 = nod_curent;
        muchie.nod2 = v[nod_curent][i].first;
        aux.push_back( muchie );
        push_heap( aux.begin(), aux.end(), compare() );
      }
    }
    while( ( ( verif[ aux.front().nod1 ] == 0 && verif[ aux.front().nod2 ] == 1 ) || ( verif[ aux.front().nod1 ] == 1 && verif[ aux.front().nod2 ] == 0 ) ) == 0 ) {
      pop_heap( aux.begin(), aux.end(), compare() );
      aux.pop_back();
    }
    apm.push_back( make_pair( aux.front().nod1, aux.front().nod2) );
    cost_apm += aux.front().cost;
    if ( apm.size() == n - 1 )
      nod_curent = -1;
    else if ( verif[ aux.front().nod1 ] == 0 )
      nod_curent = aux.front().nod1;
    else if ( verif[ aux.front().nod2 ]== 0 )
      nod_curent = aux.front().nod2;
    else
      assert( 0 );
  }
}

int main() {
  int m, i, a, b, c;
  FILE *fin, *fout;

  fin = fopen( "apm.in", "r" );                   ///citim datele
  assert( fscanf( fin, "%d%d", &n, &m) == 2 );
  for ( i = 0; i < m; i++ ) {
    assert ( fscanf( fin, "%d%d%d", &a, &b, &c ) == 3 );
    v[a].push_back( { b, c } );
    v[b].push_back( { a, c } );
  }
  fclose( fin );

  prim( 1 );  ///constuim arborele

  fout = fopen( "apm.out", "w" );
  fprintf( fout, "%d\n%d\n", cost_apm, apm.size() );
  for ( i = 0; i < apm.size(); i++ )
    fprintf( fout, "%d %d\n", apm[i].first, apm[i].second );
  fclose( fout );
  return 0;
}