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

using namespace std;

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

const int NMAX = 200000;
const int MMAX = 400000;

struct Edge{
  int a;
  int b;
  int c;

  bool operator< (Edge other) const {
    return c < other.c;
  }
};

int n, m, res;
int sef[1 + NMAX];
int ssz[1 + NMAX];
Edge v[1 + MMAX];
vector < Edge > output;

int getsef(int el) {
  if(el == sef[el])
    return el;
  else {
    sef[el] = getsef(sef[el]);
    return sef[el];
  }
}

int main()
{
  in >> n >> m;
  for(int i = 1; i <= m; i++)
    in >> v[i].a >> v[i].b >> v[i].c;
  sort(v + 1, v + m + 1);

  for(int i = 1; i <= n; i++) {
    sef[i] = i;
    ssz[i] = 1;
  }

  for(int i = 1; i <= m; i++) {
    int sx = getsef(v[i].a);
    int sy = getsef(v[i].b);

    if(sx != sy) {
      if(ssz[sy] <= ssz[sx]) {
        sef[sy] = sx;
        ssz[sx] += ssz[sy];
      } else {
        sef[sx] = sy;
        ssz[sy] += ssz[sx];
      }

      res += v[i].c;
      output.push_back(v[i]);
    }
  }

  out << res << '\n';
  out << n - 1 << '\n';

  for(int i = 0; i < output.size(); i++)
    out << output[i].a << ' ' << output[i].b << '\n';

  in.close();
  out.close();
  return 0;
}