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

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

class Edge {
public:
  int x, y;
  int cost;

  Edge() = default;

  Edge(int x, int y, int cost):
                  x(x), y(y), cost(cost) {};

  bool operator < (const Edge& other) const {
    return this->cost < other.cost;
  }
};

Edge edges[1 + MMAX];

std::vector<int> indices;

int ds[1 + NMAX];
int ds_height[1 + NMAX];

int ds_root(int x) {
  if (ds[x] == x)
    return x;

  ds[x] = ds_root(ds[x]);
  return ds[x];
}

bool ds_union(int x, int y) {
  x = ds_root(x);
  y = ds_root(y);

  if (x == y)
    return false;

  if (ds_height[x] < ds_height[y])
    ds[x] = y;
  else if (ds_height[x] == ds_height[y]) {
    ds[x] = y;
    ++ds_height[y];
  }
  else
    ds[y] = x;

  return true;
}


int main() {
  std::ifstream in("apm.in");
  std::ofstream out("apm.out");

  int n, m;
  in >> n >> m;

  for (int i = 1; i <= m; ++i)
    in >> edges[i].x >> edges[i].y >> edges[i].cost;

  std::sort(edges + 1, edges + 1 + m);

  for (int i = 1; i <= n; ++i) {
    ds[i] = i;
    ds_height[i] = 1;
  }

  int cost = 0;
  int remaining = n - 1;
  for (int i = 1; i <= m; ++i) {
    if (ds_union(edges[i].x, edges[i].y)) {
      cost += edges[i].cost;
      --remaining;
      indices.emplace_back(i);
    }
  }

  out << cost << '\n';
  out << n - 1 << '\n';
  for (auto& i: indices)
    out << edges[i].x << ' ' << edges[i].y << '\n';

  return 0;
}