#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

int n, m, t[200001], poz[200000];
struct Muchie {
  int x, y, c;
} v[400001];

int cauta (int x) {
  int y = x, aux;
  while (y != t[y])
    y = t[y];
  while (x != y) {
    aux = t[x];
    t[x] = y;
    x = aux;
  }
  return x;
}

void uneste (int x, int y) {
  x = cauta (x);
  y = cauta (y);
  t[y] = x;
}

bool cmp (Muchie a, Muchie b) {
  return a.c < b.c;
}

void kruskal () {
  int cf = 0, k = 0;
  for (int i = 1; i <= m; i++) {
    if (cauta (v[i].x) != cauta (v[i].y)) {
      cf += v[i].c;
      poz[++k] = i;
      uneste (v[i].x, v[i].y);
    }
  }
  fout << cf << '\n';
  fout << k << '\n';
  for (int i = 1; i <= k; i++)
    fout << v[poz[i]].x << ' ' << v[poz[i]].y << '\n';
}

int main()
{
  fin >> n >> m;
  for (int i = 1; i <= n; i++)
    t[i] = i;
  for (int i = 1; i <= m; i++)
    fin >> v[i].x >> v[i].y >> v[i].c;
  sort (v + 1, v + m + 1, cmp);
  kruskal ();
  return 0;
}