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

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

class Apm {
public:
  Apm (int n, int m) {
    this -> _n = n;
    this -> _m = m;
    this -> _cost = 0;
    this -> _link.resize(m + 1);
    this -> _rank.resize(n + 1);
    this -> _root.resize(n + 1);

    for (int i = 1; i <= n ; i ++) {
      _rank[i] = 1;
      _root[i] = i;
    }

    for (int i = 1; i <= _m; i ++) {
      int a, b, cost;
      cin >> a >> b >> cost;
      if (a > b)
        swap(a, b);
      this -> _link[i] = {cost, {a, b}};
    }
    sort(this -> _link.begin() + 1, this -> _link.end());
  }

  void solve() {
    for (int i = 1; i <= this -> _m; i ++) {
      int x = this -> _link[i].second.first;
      int y = this -> _link[i].second.second;
      int cost = this -> _link[i].first;

      if (_get_root(x) != _get_root(y)) {
        _link_nodes(x, y);
        _sol.push_back({x, y});
        _cost += cost;
      }
    }
  }

  void print_ans() {
    cout << _cost << '\n' << _sol.size() << '\n';
    for (auto x : _sol) {
      cout << x.first << ' ' << x.second << '\n';
    }
  }

private:
  int _n;
  int _m;
  int _cost;
  vector < pair < int, pair < int, int > > > _link;
  vector < int > _rank;
  vector < int > _root;
  vector < pair < int, int > > _sol;

  int _get_root(int x) {
    int r = x;
    while (r != _root[r]) {
      r = _root[r];
    }

    while (x != _root[x]) {
      int aux = _root[x];
      _root[x] = r;
      x = aux;
    }

    return r;
  }

  void _link_nodes(int x, int y) {
    x = _get_root(x);
    y = _get_root(y);
    
    if (_rank[x] < _rank[y]) {
      swap(x, y);
    }

    _rank[x] += _rank[y];
    _root[y] = _root[x];
  }
};

int main() {
  int n, m;
  cin >> n >> m;
  Apm *G = new Apm(n, m);

  G -> solve();
  G -> print_ans();
}