#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m;
int r[200005], t[200005];
vector<pair<int, int>> result;
vector<tuple<int, int, int>> edges;

int find(const int& x) {
  if(x == t[x]) {
    return x;
  }
  return t[x] = find(t[x]);
}

void unite(const int& x, const int& y) {
  if(r[x] > r[y]) {
    r[x] += r[y];
    t[y] = x;
    return;
  }
  r[y] += r[x];
  t[x] = y;
}

void read() {
  int x, y, z;
  f>>n>>m;
  for(int i = 1;i <= m;++i) {
    f>>x>>y>>z;
    edges.push_back({z, x, y});
  }
  f.close();
}

void solve() {
  sort(edges.begin(), edges.end());
  for(int i = 1;i <= n;++i) {
    r[i] = 1;
    t[i] = i;
  }

  int t_cost = 0;
  for(const auto& edge : edges) {
    int cost = get<0>(edge), x = get<1>(edge), y = get<2>(edge);

    if(find(x) != find(y)) {
      unite(find(x), find(y));
      t_cost += cost;
      result.push_back(make_pair(x, y));
    }
  }

  g<<t_cost<<'\n'<<result.size()<<'\n';
  for(const auto& edge : result) {
    g<<edge.first<<" "<<edge.second<<'\n';
  }
  g.close();
}

int main() {

  read();
  solve();

  return 0;
}