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