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

using namespace std;

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

const int NMAX = 2 * 1e5;
const int MMAX = 4 * 1e5;

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

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

int n, m;
int res;

int sef[1 + NMAX];
int ssz[1 + NMAX];

Edge v[1 + MMAX];

vector < Edge > output;

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

void union_el(int sefx, int sefy) {
  if(ssz[sefy] <= ssz[sefx]) {
    ssz[sefx] += ssz[sefy];
    sef[sefy] = sefx;
  } else {
    ssz[sefy] += ssz[sefx];
    sef[sefx] = sefy;
  }
}

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 sefx = get_sef(v[i].a);
    int sefy = get_sef(v[i].b);

    if(sefx != sefy) {
      union_el(sefx, sefy);

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