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

using namespace std;

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

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


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

int find ( int x ){
  int y = x, aux;

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

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

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

  return x;
}

void unite ( 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] ++;
}

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

void afis ( int x, string nume ){
  ofstream out( nume );
  out << x << " \n" << sol.size() << "\n";
  for ( auto i : sol ){
    out << i.n1 << " " << i.n2 << "\n";
  }
  out.close();
}

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

int main (){

  int i, n, m;
  Triplet aux;

  string nume1 = "date.in";
  string nume2 = "date.out";

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

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

  t = new int [n + 1];
  rang = new int [n + 1];

  for ( i = 1; i <= n; i++ )
    t[i] = i, rang[i] = 0;

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

  afis ( apm(), nume4 );

  delete [] t;
  delete [] rang;

  return 0;
}