#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;

bool cmp ( Triplet a, Triplet b ){
  return ( a.cost < b.cost );
  /*if ( a.cost < b.cost )
    return 1;
  if ( a.cost > b.cost )
    return 0;
  if ( a.cost == b.cost ){
    if ( a.n1 == b.n1)
      return ( a.n2 <= b.n2 );
    return ( a.n1 <= a.n2 );
  }*/
}

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

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

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

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

  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, char 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 n ) {
    int cost_total = 0;
    for ( auto x : v ){
        if ( not connected (x.n1, x.n2)){
          cost_total += x.cost;
          sol.push_back ( x );
          unite (x.n1 , x.n2);
        }
    }
    return cost_total;
}

int main (){

  int n, m, i;
  Triplet aux;

  char nume_in[] = "date.in";
  char nume_in2[] = "apm.in";

  char nume_out[] = "date.out";
  char nume_out2[] = "apm.out";

  ifstream in ( nume_in2 );
  in >> n >> m;

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

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

  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);

  afis ( apm(n), nume_out2 );

  v.clear ();
  sol.clear ();

  delete [] t;

  return 0;
}