#include <cstdio>
#include <vector>
#include <algorithm>

const int MAX_N = 200000;

struct Edge {
  int u;
  int v;
  int cost;
  
  bool operator <(const Edge &other) const {
    return this->cost < other.cost;
  }
};

std::vector<Edge> v;
std::vector<Edge> sol;

int t[5 + MAX_N];
int h[5 + MAX_N];

int myFind(int x) {
  while (x != t[x]) {
    x = t[x];
  }
  return x;
}

bool myUnion(int x, int y) {
  x = myFind(x);
  y = myFind(y);
  if (x == y) {
    return false;
  }
  if (h[x] == h[y]) {
    h[x]++;
    t[y] = x;
  } else if (h[x] < h[y]) {
    t[x] = y;
  } else {
    t[y] = x;
  }
  return true;
}

int main() {
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
  
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    Edge e;
    scanf("%d%d%d", &e.u, &e.v, &e.cost);
    v.push_back(e);
  }
  std::sort(v.begin(), v.end());
  
  for (int i = 1; i <= n; ++i) {
    t[i] = i;
    h[i] = 1;
  }
  
  int cost;
  cost = 0;
  for (int i = 0; i < m; ++i) {
    int n1 = myFind(v[i].u);
    int n2 = myFind(v[i].v);
    if (myUnion(n1, n2)) {
      cost += v[i].cost;
      sol.push_back(v[i]);
    }
  }
  printf("%d\n%d\n", cost, n - 1);
  for (int i = 0; i < sol.size(); ++i) {
    printf("%d %d\n", sol[i].u, sol[i].v);
  }
  return 0;
}