#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int LMAX = 400505;
const int NMAX = 200505;
struct edge {
  int a, b, cost;
};
edge A[LMAX];
int n, m, parent[NMAX], rnk[NMAX];

void read() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &A[i].a, &A[i].b, &A[i].cost);
  }
}

void makeSet(int node) {
  parent[node] = node;
  rnk[node] = 0;
}

int findSet(int node) {
  if (parent[node] == node)
    return node;
  return parent[node] = findSet(parent[node]);
}

void uniteSets(int x, int y) {
  x = findSet(x);
  y = findSet(y);
  if (x != y) {
    if (rnk[x] > rnk[y])
      swap(x, y);
    parent[x] = y;
    if (rnk[x] == rnk[y])
      rnk[y]++;
  }
}

void prepare() {
  for (int i = 1; i <= n; i++)
    makeSet(i);
  sort(A + 1, A + m + 1,
    [&] (const edge& x, const edge& y) -> bool {
      return x.cost < y.cost;
    });
}

void solve() {
  int totalCost = 0;
  vector<edge> sol;
  for (int i = 1; i <= m; i++) {
    if (findSet(A[i].a) != findSet(A[i].b)) {
      totalCost += A[i].cost;
      sol.push_back(A[i]);
      uniteSets(A[i].a, A[i].b);
    }
  }
  printf("%d\n", totalCost);
  printf("%d\n", n - 1);
  for (size_t i = 0; i < sol.size(); i++) {
    printf("%d %d\n", sol[i].a, sol[i].b);
  }
}

int main() {
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);

  read();
  prepare();
  solve();
  return 0;
}