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

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

struct Edge {
  int from;
  int to;
  int cost;
};

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<Edge> kruskal(const int n, vector<Edge> edges) {
  vector<Edge> ans;
  DSU dsu(n);

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

  for (auto edge : edges) {
    if (dsu.merge(edge.from, edge.to)) {
      ans.push_back(edge);
    }
  }

  return ans;
}

int main() {
  int n, m;
  cin >> n >> m;
  vector<Edge> 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.cost;
  }

  cout << cost << '\n';
  cout << tree.size() << '\n';
  for (auto& e : tree) {
    cout << e.from << ' ' << e.to << '\n';
  }
}