#include <cstdio>
#include <algorithm>
using namespace std;
struct Muchie {
  int u, v, c;
};
Muchie a[400005];
Muchie sol[200005];
bool cmp(Muchie a, Muchie b) {
  return a.c < b.c;
}
int t[200005];
int h[200005];
int FindSet(int x) {
  while (x != t[x])
    x = t[x];
  return x;
}
void UnionSet(int x, int y) {
  if (h[x] == h[y]) {
    h[x]++;
    t[y] = x;
  } else if (h[x] > h[y]) {
    t[y] = x;
  } else {
    t[x] = y;
  }
}
int main(){
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
  int n, m, c = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v, c1;
    scanf("%d%d%d", &u, &v, &c1);
    a[i] = {u, v, c1};
  }
  for (int i = 1; i <= n; ++i) {
    t[i] = i;
    h[i] = 1;
  }
  sort(a + 1, a + m + 1, cmp);
  int b = 0;
  for (int i = 1; i <= n && b < n - 1; ++i) {
    int tx = FindSet(a[i].u);
    int ty = FindSet(a[i].v);
    if (tx != ty) {
      c += a[i].c;
      b++;
      UnionSet(tx, ty);
      sol[b] = a[i];
    }
  }
  printf("%d\n%d\n", c, n - 1);
  for (int i = 1; i < n; ++i)
    printf("%d %d\n", sol[i].u, sol[i].v);
  return 0;
}