#include <fstream>
#include <algorithm>

using namespace std;

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

const int MAXN = 200000;
const int MAXM = 400000;

struct DisjointSetForest {
  int sef[MAXN + 1];

  void init(int n) {
    for(int i = 1; i <= n; i++) {
      sef[i] = i;
    }
  }

  int find(int i) {
    if(i == sef[i]) {
      return i;
    }
    return sef[i] = find(sef[i]);
  }

  void join(int i, int j) {
    if((i = find(i)) != (j = find(j))) {
      sef[j] = i;
    }
  }
} dsf;

struct Edge {
  int u, v, w;
} edges[MAXM + 1];
int chosen[MAXM + 1];

bool compare(Edge a, Edge b) {
  return a.w < b.w;
}

int main() {
  int n, m;
  fin >> n >> m;
  for(int i = 1; i <= m; i++) {
    fin >> edges[i].u >> edges[i].v >> edges[i].w;
  }

  sort(edges + 1, edges + m + 1, compare);

  int answer = 0, num_chosen = 0;
  dsf.init(n);
  for(int i = 1; i <= m; i++) {
    if(dsf.find(edges[i].u) != dsf.find(edges[i].v)) {
      answer += edges[i].w;
      dsf.join(edges[i].u, edges[i].v);
      chosen[i] = 1;
      num_chosen++;
    }
  }

  fout << answer << "\n" << num_chosen << "\n";
  for(int i = 1; i <= m; i++) {
    if(chosen[i]) {
      fout << edges[i].u << " " << edges[i].v << "\n";
    }
  }

  return 0;
}