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

using namespace std;

struct lucifer {
  int a;
  int b;
  int c;
};

bool operator < (lucifer a, lucifer b) {
  return a.c < b.c;
}

const int N = 200000 + 7;
int t[N];

int gami(int a) {
  if (a == t[a]) {
    return a;
  } else {
    return t[a] = gami(t[a]);
  }
}

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 <= n; i++) {
    t[i] = i;
  }
  vector <lucifer> v(m);
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", &v[i].a, &v[i].b, &v[i].c);
  }
  sort(v.begin(), v.end());

  long long pula = 0;
  vector <pair <int, int>> sol;

  for (auto &it : v) {
    int jeg1 = it.a;
    int jeg2 = it.b;
    it.a = gami(it.a);
    it.b = gami(it.b);
    if (it.a != it.b) {
      pula += it.c;
      sol.push_back({jeg1, jeg2});
      t[it.a] = it.b;
    }
  }

  printf("%lld\n%d\n", pula, n - 1);
  for (auto &x : sol) {
    printf("%d %d\n", x.first, x.second);
  }

  return 0;
}