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

using namespace std;

struct Edge
{
  int x, y;
  int cost;

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

using Graph = vector<Edge>;

int FindFather(vector<int> &fathers, int node)
{
  if (fathers[node] == -1) {
    return node;
  }
  return (fathers[node] = FindFather(fathers, fathers[node]));
}

pair<int, Graph> FindMst(Graph &g, int nodes)
{
  vector<int> fathers(nodes, -1);
  Graph mst;
  int cost = 0;

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

  for (const auto &edge : g) {
    auto father_x = FindFather(fathers, edge.x);
    auto father_y = FindFather(fathers, edge.y);

    if (father_x == father_y) {
      continue;
    }

    mst.push_back(edge);
    cost += edge.cost;
    fathers[father_y] = father_x;
  }
  return {cost, mst};
}

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

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

  Graph graph(edges);
  for (auto &edge : graph) {
    fin >> edge.x >> edge.y >> edge.cost;
    edge.x -= 1;
    edge.y -= 1;
  }

  auto res = FindMst(graph, nodes);
  fout << res.first << "\n" << res.second.size() << "\n";

  for (const auto &edge : res.second) {
    fout << edge.x + 1 << " " << edge.y + 1 << "\n";
  }
  return 0;
}