#include <bits/stdc++.h>

using namespace std;

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

const int max_n = (int)2e5 + 5;

struct Edge {
  int u, v, c;
  Edge(int _u, int _v, int _c) {
    u = _u;
    v = _v;
    c = _c;
  }
};

int n, m;

int dad[max_n], size[max_n];

vector<Edge> edges;

bool operator < (const Edge &a, const Edge &b) {
  return a.c < b.c;
}

int get(int u) {
  if (dad[u] == u) {
    return u;
  }
  return dad[u] = get(dad[u]);
}

void join(int u, int v) {
  if (size[u] > size[v]) {
    swap(u, v);
  }
  dad[u] = v;
  size[v] += size[u];
}

int main() {
  in >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, c;
    in >> u >> v >> c;
    edges.push_back(Edge(u, v, c));
  }
  sort(edges.begin(), edges.end());
  for (int i = 1; i <= n; i++) {
    dad[i] = i;
    size[i] = 1;
  }
  vector<Edge> ansTree;
  int ans = 0;
  for (Edge e : edges) {
    int u = e.u, v = e.v, c = e.c;
    u = get(u);
    v = get(v);
    if (v == u) {
      continue;
    }
    ans += c;
    join(u, v);
    ansTree.push_back(e);
  }
  out << ans << "\n" << n - 1 << "\n";
  for (Edge e : ansTree) {
    out << e.u << " " << e.v << "\n";
  }
  return 0;
}