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

using std::sort;

#define MAX_N 200000
#define MAX_M 400000

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;
cell edge[MAX_M + 1];
int adj[MAX_N + 1];
int boss[MAX_N + 1];

int 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, tmp;
  while (boss[r] != r) {
    r = boss[r];
  }
  while (u != boss[u]) {
    tmp = boss[u];
    boss[u] = r;
    u = tmp;
  }
  return r;
}

void unify(int u, int v) {
  boss[find(v)] = find(u);
}

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

  int i, u, v, cost;
  fscanf(f, "%d %d", &N, &M);
  init();
  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);

  int much = 0;
  long long int sum = 0;
  for (i = 1; i <= M; i++) {
    edge[i].cost <<= 1;
    if (find(edge[i].u) != find(edge[i].v)) {
      unify(edge[i].u, edge[i].v);
      edge[i].cost |= 1;
      sum += edge[i].cost >> 1;
      much++;
    }
  }

  freopen("apm.out", "w", stdout);
  fprintf(stdout, "%lld\n%d\n", sum, much);
  for (i = 1; i <= M && much; i++) {
    if (edge[i].cost & 1) {
      fprintf(stdout, "%d %d\n", edge[i].u, edge[i].v);
      much--;
    }
  }
  fclose(stdout);
  return 0;
}