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

#define MAX_N 200000

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

std::vector<Edge> web, tree;

int par[MAX_N];

int root(int node) {
  while (node != par[node])
    node = par[node];
  return node;
}

bool unite(int x, int y) {
  x = root(x);
  y = root(y);

  if (x == y)
    return false;

  par[x] = y;

  return true;
}

bool cmp(Edge x, Edge y) {
  return x.c < y.c;
}

int main() {
  FILE *fin, *fout;
  int n, m, x, y, c;
  int i, k, res;

  fin = fopen("apm.in", "r");

  fscanf(fin, "%d%d", &n, &m);
  for (i = 0; i < m; i++) {
    fscanf(fin, "%d%d%d", &x, &y, &c);
    web.push_back({c, x, y});
  }

  fclose(fin);

  for (i = 1; i <= n; i++)
    par[i] = i;

  std::sort(web.begin(), web.end(), cmp);

  res = 0;
  k = n - 1;
  for (i = 0; (i < m) && k; i++) {
    x = web[i].x;
    y = web[i].y;
    if (unite(x, y)) {
      res = res + web[i].c;
      k--;
    } else {
      web[i].x = 0;
    }
  }

  fout = fopen("apm.out", "w");

  fprintf(fout, "%d\n%d\n", res, (n - 1));
  for (Edge edge : web)
    if (edge.x != 0)
      fprintf(fout, "%d %d\n", edge.x, edge.y);

  fclose(fout);

  return 0;
}