#include <bits/stdc++.h>
#define maxn 200000
#define maxm 400000

using namespace std;

typedef struct
{
  int x, y, cst;
  bool up;
}muchie;

muchie v[maxm+5];
int dad[maxn+5]; /// union find noduri
int szm[maxn+5]; /// union find marime multimi

bool cmp ( muchie a, muchie b )
{
  return a.cst < b.cst;
}

int _find ( int x )
{
  int r = x, aux;
  while ( dad[r] != r )
    r = dad[r];
  /// compresie
  while ( dad[x] != r )
  {
    aux = dad[x];
    dad[x] = r;
    x = aux;
  }
  return r;
}

void _union ( int dx, int dy )
{
  if ( szm[dx] > szm[dy] )
  {
    dad[dy] = dx;
    szm[dx] += szm[dy];
    szm[dy] = 0;
  }
  else
  {
    dad[dx] = dy;
    szm[dy] += szm[dx];
    szm[dx] = 0;
  }
}

int main ()
{
  ifstream fin ( "apm.in" );
  ofstream fout ( "apm.out" );

  int n, m;

  fin >> n >> m;

  int i;

  for ( i = 0; i < m; i++ )
    fin >> v[i].x >> v[i].y >> v[i].cst;

  for ( i = 1; i <= n; i++ )
  {
    dad[i] = i;
    szm[i] = 1;
  }

  int rez = 0, na = 0, dx, dy;

  sort ( v, v + m, cmp );
  for ( i = 0; i < m; i++ )
  {
    dx = _find ( v[i].x );
    dy = _find ( v[i].y );
    if ( dx != dy )
    {
      rez += v[i].cst;
      v[i].up = 1;
      na++;
      _union ( dx, dy );
    }
  }

  fout << rez << '\n' << na << '\n';
  for ( i = 0; i < m; i++ )
    if ( v[i].up == 1 )
      fout << v[i].x << ' ' << v[i].y << '\n';

  fin.close ();
  fout.close();

  return 0;
}