#include <algorithm>
#include <fstream>
#include <tuple>
#include <vector>

using namespace std;

using Edge = tuple<int, int, int>;
using Graph = vector<Edge>;

using EdgeList = vector<pair<int, int>>;

class DSet
{
public:
  DSet(int size) : fathers_(vector<int>(size, -1)) {}

  void Unite(int a, int b);

  bool SameGroup(int a, int b);

private:
  int Root(int node);

  vector<int> fathers_;
};

void DSet::Unite(int a, int b)
{
  auto ra = Root(a);
  auto rb = Root(b);

  if (ra != rb) {
    fathers_[rb] = ra;
  }
}

bool DSet::SameGroup(int a, int b)
{
  return Root(a) == Root(b);
}

int DSet::Root(int node)
{
  if (fathers_[node] == -1) {
    return node;
  }
  return fathers_[node] = Root(fathers_[node]);
}

pair<int, EdgeList> FindMst(Graph &g, int nodes)
{
  DSet dset(nodes);
  int total_cost = 0;

  EdgeList res(nodes - 1);
  int res_ind = 0;

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

  for (const auto &e : g) {
    int cost, a, b;
    tie(cost, a, b) = e;

    if (!dset.SameGroup(a, b)) {
      dset.Unite(a, b);
      res[res_ind++] = {a, b};
      total_cost += cost;
    }
  }
  return {total_cost, res};
}

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

  int nodes, edges;
  fin >> nodes >> edges;

  Graph graph(edges);
  for (auto &e : graph) {
    int a, b, cost;
    fin >> a >> b >> cost;
    e = make_tuple(cost, a - 1, b - 1);
  }

  auto mst_pair = FindMst(graph, nodes);
  fout << mst_pair.first << "\n";
  fout << nodes - 1 << "\n";

  for (const auto &e : mst_pair.second) {
    fout << e.first + 1 << " " << e.second + 1 << "\n";
  }
  return 0;
}