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

using namespace std;

size_t PrimeAncestor(const std::vector<size_t>& Parent, size_t n)
{
  while (Parent[n] != n) n = Parent[n];
  return n;
}

/**
  @brief Kruskal's Minimum Spanning Tree (MST) algorithm with disjoint set forests
*/
template<typename ContainerT, typename GetFormerVertexF, typename GetLatterVertexF, typename OnMergeF> std::vector<size_t>
KruskalMST(const ContainerT& OrderedEdges, GetFormerVertexF former, GetLatterVertexF latter, size_t N, OnMergeF on_merge)
{
  std::vector<size_t> Parent(N);
  std::vector<size_t> MaxDepth(N, 0);
  size_t i = 0;

  // initially, the MST has no edges
  for (auto& p : Parent) p = i++;

  // add edges to the MST as long as they maintain the tree property
  for (const auto& edge : OrderedEdges) {
    size_t a = PrimeAncestor(Parent, former(edge));
    size_t b = PrimeAncestor(Parent, latter(edge));
    if (a != b) {
      if (on_merge(edge, a, b)) {
        if (MaxDepth[a] < MaxDepth[b]) Parent[a] = b;
        else if (MaxDepth[a] > MaxDepth[b]) Parent[b] = a;
        else { ++MaxDepth[a]; Parent[b] = a; }
      }
    }
  }

  return Parent;
}

int main()
{
  ifstream in("apm.in", ios::in);
  ofstream out("apm.out", ios::out);

  size_t n, m;
  in >> n >> m;

  vector<tuple<int, size_t, size_t>> edges; edges.reserve(m);
  for (size_t i=0; i < m; ++i) {
    size_t a, b;
    int c;
    in >> a >> b >> c;
    edges.emplace_back(c, a, b);
  }
  sort(begin(edges), end(edges), [](const tuple<int, size_t, size_t>& a, const tuple<int, size_t, size_t>& b) -> bool {
    return get<0>(a) < get<0>(b);
  });

  int cost = 0;
  vector<pair<size_t, size_t>> tree; tree.reserve(n-1);

  auto former = [](tuple<int, size_t, size_t> e)-> size_t { return get<1>(e); };
  auto latter = [](tuple<int, size_t, size_t> e)-> size_t { return get<2>(e); };
  auto on_merge = [&tree, &cost](tuple<int, size_t, size_t> e, size_t, size_t) { tree.emplace_back(get<1>(e), get<2>(e)); cost += get<0>(e); return true; };

  KruskalMST(edges, former, latter, n, on_merge);

  out << cost << '\n' << n-1 << '\n';
  for (const auto& e : tree) out << e.first << ' ' << e.second << '\n';

  out.close();
  return 0;
}