#include <stdio.h>
#include <algorithm>
#include <assert.h>

using std::sort;

#define MAX_N 200005
#define MAX_M 400005
#define NIL -1

struct cell {
  int u, v, cost;

  cell() {

  }

  cell(int u, int v, int cost) {
    this -> u = u;
    this -> v = v;
    this -> cost = cost;
  }
};

int N, M;
int boss[MAX_N];
cell edge[MAX_M];

bool cmp(cell a, cell b) {
  return a.cost < b.cost;
}

void init() {
  int u;
  for (u = 1; u <= N; u++) {
    boss[u] = u;
  }
}

int find(int u) {
  int r = u;
  while (r != boss[r]) {
    r = boss[r];
  }
  while (u != r) {
    int tmp = boss[u];
    boss[u] = r;
    u = tmp;
  }
  return r;
}

void unify(int u, int v) {
  int rv = find(v);
  int ru = find(u);
  if (rv > ru) {
    boss[rv] = ru;
  } else {
    boss[ru] = rv;
  }
}

int main(void) {
  FILE *f = fopen("apm.in", "r");

  int i, u, v, cost;
  fscanf(f, "%d %d", &N, &M);
  for (i = 1; i <= M; i++) {
    fscanf(f, "%d %d %d", &u, &v, &cost);
    edge[i] = cell(u, v, cost);
  }
  fclose(f);

  sort(edge + 1, edge + M + 1, cmp);

  init();

  long long total = 0;
  for (i = 1; i <= M; i++) {
    if (find(edge[i].u) != find(edge[i].v)) {
      total += edge[i].cost;
      unify(edge[i].u, edge[i].v);
      edge[i].cost = NIL;
    }
  }
/*
  for (i = 1; i <= N; i++) {
    fprintf(stderr, "%d ", boss[i]);
  }
*/
  int much = 0;
  freopen("apm.out", "w", stdout);
  fprintf(stdout, "%lld\n%d\n", total, N - 1);
  for (i = 1; i <= M; i++) {
    if (edge[i].cost == NIL) {
      if (much == N - 1) {
        assert(0);
      }
      fprintf(stdout, "%d %d\n", edge[i].u, edge[i].v);
      much++;
    }
  }
  fclose(stdout);
  return 0;
}