#include <cstdio>
#include <algorithm>
using namespace std;
const int MMAX = 400005;
const int NMAX = 200005;
struct MUCHIE
{
  int x, y;
  int cost;
};
struct SOLUTIE
{
  int x, y;
};
MUCHIE v[MMAX];
SOLUTIE sol[MMAX];
int sef[NMAX];
int h[NMAX];
bool cmp(MUCHIE first, MUCHIE second)
{
  return first.cost < second.cost;
}
int aflare_sef(int x)
{
  if(x != sef[x]) {
    return aflare_sef(sef[x]);
  }
  else {
    return x;
  }
}
bool unire(int x, int y)
{
  x = aflare_sef(x);
  y = aflare_sef(y);
  if(x != y) {
    if(h[x] < h[y]) {
      sef[x] = sef[y];
      h[y] += h[x];
    }
    else {
      sef[y] = sef[x];
      h[x] += h[y];
    }
    return true;
  }
  return false;
}

int main()
{
  int n, m;
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].cost);
  }
  sort(v + 1, v + m + 1, cmp);
  for(int i = 1; i <= n; ++i) {
    sef[i] = i;
  }
  int costt = 0;
  for(int i = 1; i <= m; ++i) {
    if(unire(v[i].x, v[i].y)) {
      costt += v[i].cost;
      sol[++sol[0].x].x = v[i].x;
      sol[sol[0].x].y = v[i].y;
    }
  }
  printf("%d\n", costt);
  printf("%d\n", sol[0].x);
  for(int i = 1; i <= sol[0].x; ++i) {
    printf("%d %d\n", sol[i].x, sol[i].y);
  }
  return 0;
}