#include <iostream>
#include <fstream>

using namespace std;

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

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

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

struct DisjointSetForest {
  int sef[MAXN + 1], comp;

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

  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;
      comp--;
    }
  }
} dsf;

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;
  }
  edges[0].w = INFINIT; // santinela

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

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

  return 0;
}