#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

const int NMAX = 2e5;
const int MMAX = 4e5;

class Edge {
public:
  int node;
  int cost;

  Edge() = default;

  Edge(int node, int cost):
    node(node), cost(cost) {};
};

std::vector<Edge> graph[1 + NMAX];

bool vis[1 + NMAX];

class QElem {
public:
  int source;
  int target;
  int edge_cost;

  QElem() = default;

  QElem(int source, int target, int edge_cost):
    source(source), target(target), edge_cost(edge_cost) {};

  bool operator < (const QElem& other) const {
    return this->edge_cost < other.edge_cost;
  }

  bool operator > (const QElem& other) const {
    return this->edge_cost > other.edge_cost;
  }
};

std::priority_queue<QElem, std::vector<QElem>, std::greater<>> pq;

int mst_cost;
std::vector<std::pair<int, int>> ans;

void prim() {
  vis[1] = true;

  for (auto& edge: graph[1])
    pq.emplace(1, edge.node, edge.cost);

  while (!pq.empty()) {
    int node = pq.top().target;
    int prev = pq.top().source;
    int cost = pq.top().edge_cost;
    pq.pop();

    if (vis[node])
      continue;

    mst_cost += cost;
    ans.emplace_back(prev, node);
    vis[node] = true;

    for (auto& edge: graph[node]) {
      if (!vis[edge.node])
        pq.emplace(node, edge.node, edge.cost);
    }
  }
}

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

  int n, m;
  in >> n >> m;

  for (int i = 1; i <= m; ++i) {
    int x, y, cost;
    in >> x >> y >> cost;

    graph[x].emplace_back(y, cost);
    graph[y].emplace_back(x, cost);
  }

  prim();

  out << mst_cost << '\n';
  out << n - 1 << '\n';
  for (auto& edge: ans)
    out << edge.first << " " << edge.second << '\n';

  return 0;
}