#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;


struct Triplet {
  int n1, n2, cost;
};

vector <Triplet> sol;
vector <Triplet> v;
int *t, *rang;
int n;


bool cmp ( Triplet a, Triplet b ){
  return ( a.cost == b.cost );
}

void united ( int x, int y ){
  x = t[x];
  y = t[y];
  if ( rang[x] > rang[y] )
    t[y] = x;
  else t[x] = y;
  if ( rang[x] == rang[y] )
    rang[x] ++;
}

int find ( int x){

  int y = x;

  if ( t[x] == x)
    return x;

  while ( y != t[y] )
    y = t[y];

  int aux;
  while ( x != t[x]){
    aux = t[x];
    t[x] = y;
    x = aux;
  }
  return x;
}

bool connected ( int a, int b){
  int x = find ( a );
  int y = find ( b );
  return ( x == y);
}

int apm (){
  int ct = 0;
  for ( auto i : v )
    if ( not connected (i.n1, i.n2)){
      ct += i.cost;
      sol.push_back(i);
      united ( i.n1, i.n2);
    }
  return ct;
}

int main(){
  string nume1 = "date.in";
  string nume2 = "apm.in";

  string nume3 = "date.out";
  string nume4 = "apm.out";

  int m, i;
  Triplet aux;

  ifstream in (nume2);
  in >> n >> m;
  for ( i = 0; i < m; i++ ){
    in >> aux.n1 >> aux.n2 >> aux.cost;
    v.push_back (aux);
  }
  in.close();

  sort ( v.begin(), v.end(), cmp);

  t = new int [n + 1];
  rang = new int[ n + 1];
  for ( i = 1; i <= n; i++ ) {
    t[i] = i;
    rang[i] = 0;
  }

  ofstream out (nume4);
  out << apm() << "\n" << sol.size() << "\n";
  for ( auto s : sol )
    out << s.n1 << " " << s.n2 << "\n";
  out.close();

  return 0;
}