#include <algorithm>
#include <fstream>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int m, n;

struct Muchie {
  int x = 0, y = 0, c = 0;
};

vector<Muchie> muchii;
vector<Muchie> rez;
vector<bool> viz;
vector<int> tata;
vector<int> h;

int Find(int u) {
  if (u == tata[u])
    return u;
  return Find(tata[u]);
}
void Union(int u, int v) {
  int ru, rv;
  ru = Find(u);
  rv = Find(v);

  if (h[ru] > h[rv]) {
    tata[rv] = ru;
  } else {
    tata[ru] = rv;
    if (h[ru] == h[rv])
      h[ru]++;
  }
}

int main() {
  f >> n >> m;
  viz.resize(n + 1);
  tata.resize(n + 1);
  h.resize(n + 1);
  for (int i = 0; i < m; i++) {
    Muchie muchie;
    f >> muchie.x >> muchie.y >> muchie.c;
    muchii.push_back(muchie);
  }
  sort(muchii.begin(), muchii.end(),
       [](Muchie a, Muchie b) { return a.c < b.c; });

  for (int i = 1; i <= n; i++) {
    tata[i] = i;
    h[i] = 1;
  }
  int nr = 0;
  for (auto muchie : muchii) {
    if (Find(muchie.x) != Find(muchie.y)) {
      rez.push_back(muchie);
      Union(muchie.x, muchie.y);
      nr++;
      if (nr == n - 1)
        break;
    }
  }

  int s;
  s = accumulate(rez.begin(), rez.end(), 0,
                 [](int acc, Muchie a) { return acc + a.c; });

  g << s << '\n' << rez.size() << '\n';
  for (auto muchie : rez) {
    g << muchie.x << ' ' << muchie.y << '\n';
  }

  return 0;
}