#include <fstream>
#include <vector>
#include <queue>

using namespace std;

struct muchie {
  int x, y, c;
}arb[200005];

struct cmp {
  bool operator() (const muchie &a, const muchie &b) const {
    return (a.c > b.c);
  }
};

int n, muchii, p[200005], rang[200005], nms, cost_total;
priority_queue<muchie, vector<muchie>, cmp>pq;

void init() {
  for (int i = 1; i <= n; i++)
    p[i] = i;
}

void uniune(int r1, int r2) {
  if (rang[r1] > rang[r2])
    p[r2] = r1;
  else {
    p[r1] = r2;
    if (rang[r1] == rang[r2])
      rang[r2]++;
  }
}

int findset(int x) {
  while (p[x] != x)
    x = p[x];
  return x;
}

int main () {
  ifstream fi("apm.in");
  ofstream fo("apm.out");
  fi >> n >> muchii; muchie m; init();
  for (int i = 1; i <= muchii; i++)
    fi >> m.x >> m.y >> m.c, pq.push(m);
  for (; nms < n-1;) {
    m = pq.top(); pq.pop();
    if (findset(m.x) != findset(m.y)) {
      nms++;
      cost_total += m.c;
      arb[nms] = m;
      uniune(findset(m.x), findset(m.y));
    }
  }
  fo << cost_total << '\n' << n-1 << '\n';
  for (int i = 1; i <= n-1; i++)
    fo << arb[i].x << ' ' << arb[i].y << '\n';
  return 0;
}