/* Se determina un arbore partial minim. */

#include <fstream>
#include <iostream>
#include <climits>

#define LIM_M 400001
#define LIM_N 200001

using namespace std;

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

struct muchie {
  int inc; int sf; int cost;
};

muchie sm[LIM_M], arbore[LIM_M];
int n, m, nms, csfm, comp[LIM_N], j, ca;

void citire () {
  int i;

  fin >> n >> m;
  for (i = 1; i <= m; i++)
    fin >> sm[i].inc >> sm[i].sf >> sm[i].cost;
}

void initcomp () {
  int i;

  for (i = 1; i <= n; i++)
    comp[i] = i;
}

void sortm () {
  int i;
  bool AmSchimbat;
  muchie aux;

  do {
    AmSchimbat = false;
    for (i = 1; i <= m-1; i++)
      if (sm[i].cost > sm[i+1].cost) { // Nu sunt in ordinea corecta
         aux = sm[i]; sm[i] = sm[i+1]; sm[i+1] = aux; AmSchimbat = true;
      }
  } while (AmSchimbat);
}

void rezultat () {
  fout << ca << '\n' << n - 1 << '\n';
  for (int i = 1; i <= nms; i++) // pentru toate muchiile selectate
    fout << arbore[i].inc << ' ' << arbore[i].sf << '\n';
}

int main () {
  int i;

  citire();
  initcomp();
  sortm();
  for (i = 1; nms <= n-2; i++) { // Se vor selecta n-1 muchii.
    if (comp[sm[i].inc] != comp[sm[i].sf]) { // Extremitatile muchiei curente sunt in componente conexe diferite.
      nms++; // Selectam inca o muchie.
      arbore[nms] = sm[i]; // Retinem muchia in arbore.
      ca += arbore[nms].cost;
      csfm = comp[sm[i].sf]; // Retinem numarul de componenta al sfarsitului muchiei
      for (j = 1; j <= n; j++) // Actualizam numerele de componenta conexa.
        if (comp[j] == csfm)
          comp[j] = comp[sm[i].inc];
    }
  }
  rezultat();
}

/* Fisierul de date corespunzator prezentarii Powerpoint:
8 13
1 2 2
1 3 9
1 4 3
1 7 6
2 5 4
3 5 5
3 6 3
4 7 2
4 8 1
5 6 7
6 7 8
6 8 4
7 8 2
*/