#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

#define DIM 200000

int sef[DIM + 1], n, nrm, total;
struct nanu {
  int x, y, cost;
}M[DIM * 2 + 1];
vector <pair<int, int>> apm;

static inline bool cmp(nanu a, nanu b) {
  return (a.cost < b.cost);
}

static inline int radacina(int nod) {
  if(sef[nod] == nod)
    return nod;
  return sef[nod] = radacina(sef[nod]);
}

static inline void Union(int a, int b) {
  if(sef[a] > sef[b])
    sef[a] = sef[b];      //retin seful minim;
  else sef[b] = sef[a];
}

static inline void Kruskal() {
  for(int i = 1; i <= nrm; i++) {
    int rad1 = radacina(M[i].x);
    int rad2 = radacina(M[i].y);
    if(rad1 != rad2) {
      Union(rad1, rad2);
      total += M[i].cost;
      apm.push_back({M[i].x, M[i].y});
    }
  }
}

int main() {
  fin >> n >> nrm;
  for(int i = 1; i <= nrm; i++)
    fin >> M[i].x >> M[i].y >> M[i].cost;

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

  //sortez muchiile crescator dupa cost;
  sort(M + 1, M + nrm + 1, cmp);

  Kruskal();
  
  fout << total << '\n';
  fout << apm.size() << '\n';
  for(auto e : apm)
    fout << e.first << " " << e.second << '\n';

    return 0;
}