#include <fstream>
#include <algorithm>

using namespace std;

struct muchie {
 int cost;
 int a, b;
 bool operator<(const muchie& alt) const {
  return this->cost < alt.cost;
 }
};

const int N = 2e5 + 1, M = 4e5;

int sef[N];
muchie mc[M], rez[N];

int sefsuprem(int nod) {
 if (sef[nod] == nod)
  return nod;
 return sef[nod] = sefsuprem(sef[nod]);
}

bool unire(int a, int b) {
 int sef_a, sef_b;
 sef_a = sefsuprem(a);
 sef_b = sefsuprem(b);
 if (sef_a == sef_b)
  return false;
 sef[sef_a] = sef_b;
 return true;
}

int main() {
 ifstream in("apm.in");
 ofstream out("apm.out");

 int n, m;
 in >> n >> m;
 for (int i = 1; i <= n; ++i)
  sef[i] = i;
 for (int i = 0; i < m; ++i)
  in >> mc[i].a >> mc[i].b >> mc[i].cost;
 sort(mc, mc + m);
 int poz = 0, cost = 0;
 for (int i = 0; i < n - 1; ++i) {
  while (!unire(mc[poz].a, mc[poz].b))
   ++poz;
  cost += mc[poz].cost;
  rez[i] = mc[poz];
  ++poz;
 }
 out << cost << '\n' << n - 1 << '\n';
 for (int i = 0; i < n - 1; ++i)
  out << rez[i].a << ' ' << rez[i].b << '\n';

 in.close();
 out.close();
 return 0;
}