#include <fstream>
#include <queue>
#include <vector>

#include <iostream>

using namespace std;

struct Node
{
  int cost = (1 << 25);
  bool used = false;
  vector<pair<int, int>> edges;
};

using Graph = vector<Node>;

struct Edge
{
  int x, y;
  int cost;

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

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

pair<int, Mst> FindMst(Graph &g)
{
  priority_queue<Edge> heap;
  heap.push({-1, 0, 0});
  g[0].cost = 0;

  int total_cost = 0;
  Mst mst;

  while (!heap.empty()) {
    auto x = heap.top().x;
    auto y = heap.top().y;
    auto cost = heap.top().cost;
    heap.pop();

    if (g[y].used) {
      continue;
    }

    g[y].used = true;
    total_cost += cost;

    if (x >= 0) {
      mst.push_back({x, y});
    }

    for (const auto &edge : g[y].edges) {
      auto next = edge.first;
      auto new_cost = edge.second;

      if (!g[next].used && new_cost < g[next].cost) {
        g[next].cost = new_cost;
        heap.push({y, next, new_cost});
      }
    }
  }
  return {total_cost, mst};
}

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

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

  Graph graph(nodes);
  for (int i = 0; i < edges; ++i) {
    int x, y, cost;
    fin >> x >> y >> cost;

    graph[x - 1].edges.push_back({y - 1, cost});
    graph[y - 1].edges.push_back({x - 1, cost});
  }

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

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