#include <cstdio>
#include <algorithm>
using namespace std;

struct muchie {
  int x, y;
  int cost;
};

const int NMAX = 200000;
const int MMAX = 400000;

muchie v[1 + MMAX];
int tata[1 + NMAX];
bool luat[1 + MMAX];

int radacina(int x) {
  while (tata[x] != tata[tata[x]])
	tata[x] = tata[tata[x]];
  return tata[x];
}

bool alipire(int x, int y) {
  int tx = radacina(x), ty = radacina(y);

  if (tx != ty) {
    tata[tx] = ty;
    return true;
  }

  return false;
}

bool comp (muchie a, muchie b) {
  return a.cost < b.cost;
}

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)
    tata[i] = i;
  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, comp);

  int cost = 0;
  for (int i = 1; i <= m; ++i) {
    if (alipire(v[i].x, v[i].y))
    {
      cost += v[i].cost;

      luat[i] = true;
    }
  }

  printf("%d\n%d\n", cost, n - 1);
  for(int i = 1; i<= m; ++i)
    if (luat[i])
      printf("%d %d\n", v[i].y, v[i].x);

  return 0;
}