#include <cstdio>
#include <algorithm>

const int MAX_N = 200000;
const int MAX_M = 400000;
int sef[1+MAX_N];
int apm[MAX_N];
struct Edge {
  int a, b, cost;
}v[MAX_M];

int myfind(int x) {
  int rez;
  if(x == sef[x])
    return x;
  rez = myfind(sef[x]);
  sef[x] = rez;
  return rez;
}

void myunion(int a, int b) {
  sef[myfind(a)] = myfind(b);
}

bool cmp(Edge a, Edge b) {
  return a.cost < b.cost;
}

int main() {
  int n, m, e, cost;
  FILE *fin = fopen("apm.in", "r");
  fscanf(fin, "%d%d", &n, &m);
  for(int i = 0; i < m; ++i)
    fscanf(fin, "%d%d%d", &v[i].a, &v[i].b, &v[i].cost);
  fclose(fin);

  for(int i = 1; i <= n; ++i)
    sef[i] = i;

  std::sort(v, v + m, cmp);
  e = 0;
  int i = 0;
  cost = 0;
  while(i < m && e < n - 1) {
    if(myfind(v[i].a) != myfind(v[i].b)) {
      cost = cost + v[i].cost;
      apm[e] = i;
      e++;
      myunion(v[i].a, v[i].b);
    }
    ++i;
  }

  FILE *fout = fopen("apm.out", "w");
  fprintf(fout, "%d\n%d\n", cost, n - 1);
  for(int i = 0; i < n - 1; ++i)
    fprintf(fout, "%d %d\n", v[i].a, v[i].b);
  fclose(fout);
  return 0;
}