#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int const nmax = 200000;

struct Edge {
  int x, y, cost;
  bool operator < (Edge other) const{
    return cost > other.cost;
  }
};

priority_queue <Edge> q;
vector <int> mark(1 + nmax);
vector <int> sol;
vector < vector<int> > mult;

void init(int n) {
  vector <int> aux;
  aux.push_back(0);
  mult.push_back(aux);
  for(int i = 1; i <= n; ++ i) {
    aux[0] = i;
    mark[i] = i;
    mult.push_back(aux);
  }
}

void union1(int x, int y) {
  if(mult[x].size() < mult[y].size()) {
    for(int i=0; i<mult[x].size(); i++) {
      mark[mult[x][i]] = mark[mult[y][0]];
      mult[y].push_back(mult[x][i]);
    }
  } else {
    for(int i=0; i<mult[y].size(); i++) {
      mark[mult[y][i]] = mark[mult[x][0]];
      mult[x].push_back(mult[y][i]);
    }
  }
}

int main() {
  int n, m;
  in >> n >> m;
  init(n);

  for(int i = 1; i <= m; ++ i) {
    int x, y, cost;
    in >> x >> y >> cost;
    q.push({x, y, cost});
  }

  int rasp = 0;
  while(!q.empty()) {

    if(mark[q.top().x] != mark[q.top().y]) {
      union1(mark[q.top().x], mark[q.top().y]);
      sol.push_back(q.top().x);
      sol.push_back(q.top().y);
      rasp += q.top().cost;
    }
    q.pop();
  }

  out << rasp << '\n' << sol.size() / 2 << '\n';
  for(int i = 0; i < sol.size() - 1; i += 2) {
    out << sol[i] << " " << sol[i + 1] << '\n';
  }
  return 0;
}