#include <bits/stdc++.h>
#include <utility>
#include <vector>
using namespace std;

#ifdef INFOARENA
ifstream fin("apm.in");
ofstream fout("apm.in");
#define cin fin
#define cout fout
#endif

struct Neighbor {
  int node;
  int cost;
};

using Graph = vector<vector<Neighbor>>;

struct DSU {
  vector<int> size;
  vector<int> papi;

  DSU(int n) : size(n + 1), papi(n + 1) {
    fill(size.begin(), size.end(), 1);
    iota(papi.begin(), papi.end(), 0);
  }

  int find(int node) {
    if (papi[node] == node)
      return node;
    
    return papi[node] = find(papi[node]);
  }

  bool merge(int x, int y) {
    int comp_x = find(x);
    int comp_y = find(y);

    if (comp_x == comp_y)
      return false;

    if (size[comp_x] > size[comp_y])
      swap(comp_x, comp_y);

    size[comp_y] += size[comp_x];
    papi[comp_x] = comp_y;
    return true;
  }
};

vector<pair<int, Neighbor>> kruskal(const int n, vector<pair<int, Neighbor>> edges) {
  vector<pair<int, Neighbor>> ans;
  DSU dsu(n);

  sort(edges.begin(), edges.end(), [](auto e1, auto e2){
    return e1.second.cost < e2.second.cost;
  });

  for (auto [from, neigh] : edges) {
    if (dsu.merge(from, neigh.node)) {
      ans.emplace_back(from, neigh);
    }
  }

  return ans;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<pair<int, Neighbor>> edges;

  for (int i = 1; i <= m; i++) {
    int from, to, cost; cin >> from >> to >> cost;
    edges.push_back({ from, { to, cost } });
    edges.push_back({ to, { from, cost }});
  }

  auto tree = std::move(kruskal(n, edges));

  int cost = 0;
  for (auto& e : tree) {
    cost += e.second.cost;
  }

  cout << cost << '\n';
  cout << tree.size() << '\n';
  for (auto& e : tree) {
    cout << e.first << ' ' << e.second.node << '\n';
  }
}