#include <iostream>

#include <algorithm>
#include <queue>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

template <class T>
class disjoint_set {
  public:
    template <class Iterator>
    explicit disjoint_set(Iterator begin, Iterator end) {
      for (auto it = begin; it != end; ++it) {
        parent[*it] = *it;
        rank[*it] = 0;
      }
    }

    T find(const T& x) {
      if (x == parent[x])
        return x;
      return parent[x] = find(parent[x]);
    }

    void unite(const T& x, const T& y) {
      auto px = find(x);
      auto py = find(y);

      if (rank[px] < rank[py]) {
        parent[px] = py;
      } else if (rank[px] > rank[py]) {
        parent[py] = px;
      } else {
        parent[py] = px;
        ++rank[px];
      }
    }

    bool same_component(const T& x, const T& y) const {
      return find(x) == find(y);
    }

  private:
    unordered_map<T, T> parent;
    unordered_map<T, int> rank;
};

template <class T>
struct edge {
  T src, dst;
  double cost;

  explicit edge(T src_, T dst_, double cost_)
    : src(src_), dst(dst_), cost(cost_) {}

  T get_src() const { return src; }
  T get_dst() const { return dst; }
  double get_cost() const { return cost; }

  bool operator<(const edge& rhs) const {
    return get_cost() < rhs.get_cost();
  }

  bool operator>(const edge& rhs) const {
    return get_cost() > rhs.get_cost();
  }
};

// Directed graph class
template <class T>
class digraph {
public:
  void add_node(T node) { nodes.insert(node); }

  void add_edge(T src, T dst) {
    add_node(src), add_node(dst);
    adjlist[src].emplace_back(src, dst, 0);
    edgelist.emplace_back(src, dst, 0);
  }
  void add_edge(T src, T dst, double cost) {
    add_node(src), add_node(dst);
    adjlist[src].emplace_back(src, dst, cost);
    edgelist.emplace_back(src, dst, cost);
  }

  // topological sort
  vector<T> topsort() const {
    unordered_map<T, int> in_degree;
    for (const auto& edges : adjlist) {
      for (const auto& e : adjlist.second)
        in_degree[e.dst]++;
    }

    queue<T> q;
    for (const auto& node : nodes)
      if (in_degree[node] == 0)
        q.push(node);

    vector<T> result;
    while (!q.empty()) {
      auto node = q.front();
      q.pop();
      result.push_back(node);

      for (const auto& e : adjlist[node]) {
        --in_degree[e.dst];
        if (in_degree[e.dst] == 0)
          q.push(e.dst);
      }
    }

    for (const auto& node : nodes)
      if (in_degree[node] != 0)
        return vector<T>();
    return result;
  }

  // dijkstra cost (pairs of node, distance to node)
  unordered_map<T, double> dijkstra_cst(const T& src) {
    unordered_set<T> vis;
    unordered_map<T, double> dist;
    priority_queue<pair<double, T>, vector<pair<double, T>>,
        greater<pair<double, T>>> pq;

    for (const auto& node : nodes)
      dist[node] = numeric_limits<double>::max();
    dist[src] = 0;
    pq.emplace(0, src);

    while (!pq.empty()) {
      auto p = pq.top();
      pq.pop();

      auto node = p.second;
      if (vis.count(node))
        continue;
      vis.insert(node);

      for (const auto& e : adjlist[node]) {
        if (dist[node] + e.cost < dist[e.dst]) {
          dist[e.dst] = dist[node] + e.cost;
          pq.emplace(dist[e.dst], e.dst);
        }
      }
    }

    return dist;
  }

  // minimum spanning tree
  vector<edge<T>> min_span_tree() {
    auto ds = disjoint_set<T>(nodes.begin(), nodes.end());

    vector<edge<T>> result;
    sort(edgelist.begin(), edgelist.end());
    for (const auto& e : edgelist) {
      if (ds.find(e.src) != ds.find(e.dst)) {
        result.push_back(e);
        ds.unite(e.src, e.dst);
      }
    }

    return result;
  }

  // strongly connected components

private:
  unordered_set<T> nodes;
  unordered_map<T, vector<edge<T>>> adjlist;
  vector<edge<T>> edgelist;
};

int main()
{
  int n, m;
  cin >> n >> m;

  digraph<int> g;
  for (int i = 1; i <= n; ++i)
    g.add_node(i);
  for (int i = 1; i <= m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    g.add_edge(a, b, c);
    g.add_edge(b, a, c);
  }

  auto res = g.min_span_tree();
  int cost = 0;
  for (auto v : res)
    cost += v.cost;
  cout << cost << "\n";
  cout << res.size() << "\n";
  for (auto v : res) {
    cout << v.src << " " << v.dst << "\n";
  }

  return 0;
}