#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin  ("apm.in");
ofstream fout ("apm.out");

int N, M;
int t[200003], c[200003];

void Initializare()
{
    int i, j;
    fin >> N >> M;
    for (i=1; i<=N; i++)
       t[i] = 0, c[i] = 1;
}

int Find(int x)
{
  int y, z;
  y=x;
  while (t[x]!=0)
     x=t[x];

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

void Union(int x, int y)
{
   if (c[x] > c[y])
   {
      c[x] += c[y];
      c[y] = 0;
      t[y] = x;
   }
   else // c[y] <c[x]
   {
      c[y] += c[x];
      c[x] = 0;
      t[x] = y;
   }
}

struct coord
{
   int x, y, c;
};

inline bool cmp(const coord nr1, const coord nr2)
{
   return (nr1.c < nr2.c);
}

coord muchii[400003];

void Citire()
{
  coord w;
  int i, j;
  for (i=1; i<=M; i++)
   {
      fin >> w.x >> w.y >> w.c;
      muchii[i]=w;
   }
}

void Sortare()
{
  sort(muchii+1, muchii+M+1, cmp);
}

void Rezolva()
{
  int i, j, x, y, cnt=0, c=0, s=0;
  for (i=1; i<=M; i++)
  {
     x = muchii[i].x; y = muchii[i].y; c = muchii[i].c;
     if (Find(x) != Find(y)) /// adaug muchia
      {
          cnt++;
          Union(Find(x), Find(y));
          s += c;
          muchii[i].c = -2500;
      }
  }
     /// le-am rezolvat
     /// acum mai avem sa le afisam
  fout << s << "\n";
  fout << cnt << "\n";

  for (i=1; i<=M; i++)
  {
     if (muchii[i].c == -2500)
     fout << muchii[i].x << " " << muchii[i].y << "\n";
  }
}

int main ()
{
  Initializare();
  Citire();
  Sortare();
  Rezolva();
  fin.close();
  fout.close();
  return 0;
}