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

using namespace std;

int find(vector<pair<int, int>>& p, int x) {
  if (x == p[x].first) {
    return x;
  }
  p[x].first = find(p, p[x].first);
  return p[x].first;
}

void unite(vector<pair<int, int>>& p, int x, int y) {
  x = find(p, x);
  y = find(p, y);

  if (p[x].second > p[y].second) {
    p[y].first = x;
  } else {
    p[x].first = y;
  }

  if (p[x].second == p[y].second)
    ++p[y].second;
}

bool same_set(vector<pair<int, int>>& p, int x, int y) {
  return find(p, x) == find(p, y);
}

int main() {
  vector<pair<int, int>> disjoint;
  vector<tuple<int, int, int>> graph;
  vector<pair<int, int>> ans;
  ifstream fin("apm.in");
  ofstream fout("apm.out");
  int n, m, cost = 0;

  fin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int x, y, cost;
    fin >> x >> y >> cost;
    graph.push_back(make_tuple(cost, x, y));
  }

  disjoint.resize(n + 1);
  sort(graph.begin(), graph.end());

  for (size_t iter = 0; iter < disjoint.size(); ++iter) {
    disjoint[iter].first = iter;
  }

  for (auto edge : graph) {
    if (!same_set(disjoint, get<1>(edge), get<2>(edge))) {
      cost += get<0>(edge);
      ans.push_back({get<1>(edge), get<2>(edge)});
      unite(disjoint, get<1>(edge), get<2>(edge));
    }
  }

  fout << cost << "\n" << ans.size() << "\n";
  for (auto edge : ans)
    fout << edge.first << " " << edge.second << "\n";

  return 0;
}