#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int n, m;
vector<tuple<int, int, int>> edges;
int t[200001], r[200001];

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

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;
}

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

  return t[x] = find(t[x]);
}

void solve() {
  int cost = 0;
  vector<pair<int, int>> result_e;
  sort(edges.begin(), edges.end());

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

    if(find(x) != find(y)) {
      result_e.push_back({x, y});
      cost += c;
      unite(find(x), find(y));
    }
  }

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

int main() {
  read();
  solve();
  return 0;
}