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

using namespace std;

const int nmax = 1e5;

struct Edge {
  int to, from, cost;

  bool operator<(const Edge &other) { return cost < other.cost; }
};

struct DisjointSetUnion {
public:
  DisjointSetUnion(int n) : n(n) {
    for (int i = 1; i <= n; i++) {
      parent[i] = i;
      comp[i] = i;
      sz[i] = 1;
    }
  }

  int find(int x) {
    if (parent[x] == x)
      return x;
    return parent[x] = find(parent[x]);
  }

  void unite(int x, int y) {
    x = find(x);
    y = find(y);

    if (x == y)
      return;

    if (sz[x] < sz[y])
      swap(x, y);

    parent[y] = x;
    sz[x] += sz[y];
    comp[y] = comp[x];
  }

public:
  int comp[nmax + 1];

private:
  int n, parent[nmax + 1], sz[nmax + 1];
};

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

int n, m, u, v, w, cost;
vector<Edge> edges, apm;

int main() {
  fin >> n >> m;
  while (m--) {
    fin >> u >> v >> w;

    edges.push_back({u, v, w});
    edges.push_back({v, u, w});
  }

  DisjointSetUnion links(n);

  sort(edges.begin(), edges.end());

  for (auto edge : edges) {
    if (links.find(edge.to) != links.find(edge.from)) {
      links.unite(edge.to, edge.from);

      cost += edge.cost;
      apm.push_back(edge);
    }
  }

  fout << cost << '\n' << apm.size() << '\n';
  for (auto edge : apm) {
    fout << edge.to << ' ' << edge.from << '\n';
  }
  return 0;
}