#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define INPUT "apm.in"
#define OUTPUT "apm.out"
#define pb push_back

const long NMAX = 200001;

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

long N, M, Final;
long Nod1[ NMAX ], Nod2[ NMAX ], Cost[ NMAX ], Deg[ NMAX ];
vector<long> Poz, Rez;

void readData()
{
  fscanf(fin, "%ld %ld", &N, &M);

  for(long i = 1; i <= M; ++i)
  {
    fscanf(fin, "%ld %ld %ld", Nod1+i, Nod2+i, Cost+i);

    Poz.pb(i);
  }

  for(long i = 1; i <= N; ++i)
    Deg[ i ] = i;
}

inline int cmp(long _X, long _Y)
{
  return Cost[ _X ] < Cost[ _Y ];
}

long root(long _X)
{
  if(Deg[ _X ] == _X ) return _X;
  else return root(Deg[ _X ]);
  return Deg[ _X ];
}

void group(long _X, long _Y)
{
  Deg[ root(_X) ] = root(_Y);
}

void solve()
{
  for(long i = 1; i <= M; ++i)
  {
    if(root( Nod1[ Poz[ i - 1 ] ] ) != root( Nod2[ Poz[ i - 1 ] ]))
    {
      Final += Cost[ Poz[ i - 1 ] ];
      group( Nod1[ Poz[ i - 1 ] ], Nod2[ Poz[ i - 1 ] ] );
      Rez.pb(Poz[ i - 1 ]);
    }
  }

  fprintf(fout, "%ld\n%ld\n", Final, N-1);
  for(long i = 0; i < N-1; ++i)
    fprintf(fout, "%ld %ld\n", Nod1[ Rez[ i ] ], Nod2[ Rez[ i ] ]);
}

int main()
{
  readData();

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

  solve();

  fclose(fin);
  fclose(fout);

  return 0;
}