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

struct Edge {
  int from, to, cost;
  Edge(int from, int to, int cost): from(from), to(to), cost(cost) {}
};
struct EdgeComparator {
  bool operator()(Edge& e1, Edge& e2) {
    return e1.cost > e2.cost;
  }
};

int main() {
  std::ifstream in("apm.in");
  std::ofstream out("apm.out");
  
  int n, m;
  in >> n >> m;
  
  std::vector<std::vector<Edge>> graph;
  std::vector<bool> isInTree;
  graph.reserve(n);
  isInTree.reserve(n);
  for (int i = 0; i < n; i++) {
    graph.push_back(std::vector<Edge>());
    isInTree.push_back(false);
  }
  for (int i = 0; i < m; i++) {
    int from, to, cost;
    in >> from >> to >> cost;
    graph[from - 1].push_back(Edge(from, to, cost));
    graph[to - 1].push_back(Edge(to, from, cost));
  }
  
  std::priority_queue<Edge, std::vector<Edge>, EdgeComparator> q;
  for (Edge& e : graph[0]) q.push(e);
  isInTree[0] = true;
  
  std::vector<Edge> minTree;
  minTree.reserve(m - 1);
  int totalCost = 0;
  while (minTree.size() != n - 1) {
    Edge best = q.top();
    q.pop();
    if (!isInTree[best.to - 1]) {
      totalCost += best.cost;
      isInTree[best.to - 1] = true;
      minTree.push_back(best);
      for (Edge& incident : graph[best.to - 1]) {
        if (!isInTree[incident.to - 1]) {
          q.push(incident);
        }
      }
    }
  }
  
  out << totalCost << "\n";
  out << minTree.size() << "\n";
  for (Edge& e : minTree) {
    out << e.from << " " << e.to << "\n";
  }
  
  return 0;
}