#include <cstdio>

using namespace std;

FILE *input, *output;

#define NMAX 200002
#define MMAX 400002

int T[NMAX], H[NMAX];

void Union(int x, int y);
int Find(int x);

typedef struct {
  int x, y, cost;
} muchie;
muchie M[MMAX];
struct {
  int x, y;
} solutie[MMAX];

void inserare(muchie H[], int &n, muchie x);
void combinare(muchie H[], int n, int i);
muchie extragere(muchie H[], int &n);

int sum;
int n, m;

int main(void) { int i;
	input = fopen("apm.in", "r"), output = fopen("apm.out", "w");

	(void)fscanf(input, "%d %d", &n, &m);
  for (i = 1; i <= m; ++i) {
    (void)fscanf(input, "%d %d %d", &M[i].x, &M[i].y, &M[i].cost);
  }

  for (i = m/2; i >= 1; --i) combinare(M, m, i);

  int rx, ry; muchie a;
  n = 0;
  while (m > 0) {
    a = extragere(M, m);
    rx = Find(a.x);
    ry = Find(a.y);
    if (rx != ry) {
      sum += a.cost;

      ++n;
      solutie[n].x = a.x;
      solutie[n].y = a.y;

      Union(rx, ry);
    }
  }

  (void)fprintf(output, "%d\n", sum);
  (void)fprintf(output, "%d\n", n);
  for (i = 1; i <= n; ++i) (void)fprintf(output, "%d %d\n", solutie[i].x, solutie[i].y);

	fclose(output);
	return 0;
}


muchie extragere(muchie H[], int &n) {
  muchie x = H[1];
  H[1] = H[n]; --n;
  combinare(H, n, 1);
  return x;
}

void combinare(muchie H[], int n, int i) {
  muchie x = H[i];
  int tata = i, fiu = 2 * tata;
  while (fiu <= n) {
    if (fiu+1 <= n && H[fiu].cost > H[fiu+1].cost) ++fiu;
    if (x.cost > H[fiu].cost) {
      H[tata] = H[fiu];
      tata = fiu;
      fiu = 2 * tata;
    } else break;
  }

  H[tata] = x;
}

void inserare(muchie H[], int &n, muchie x) {
  int fiu = n+1, tata = fiu / 2;
  while (tata && H[tata].cost > x.cost) {
    H[fiu] = H[tata];
    fiu = tata;
    tata = fiu / 2;
  }

  H[fiu] = x; ++n;
}


void Union(int x, int y) {
  if (H[x] > H[y]) T[y] = x;
  else if (H[x] < H[y]) T[x] = y;
  else {
    T[y] = x;
    ++H[x];
  }
}

int Find(int x) {
  if (T[x] == 0) return x;
  T[x] = Find(T[x]);
  return T[x];
}