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

using namespace std;

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

struct Muchie
{
  int x;
  int y;
  int cost;

  Muchie() {};

  Muchie(int x, int y, int cost) :
    x(x), y(y), cost(cost) {}

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

};

Muchie muchii[1 + MMAX];

int tata[1 + NMAX];
int h[1 + NMAX];

vector<int> muchiiSol;

int n, m;

void init()
{
  for (int i = 1; i <= n; ++i)
  {
    tata[i] = i;
    h[i] = 1;
  }
}

int GetFather(int x)
{
  if (tata[x] == x)
    return x;

  tata[x] = GetFather(tata[x]);

  return tata[x];
}

bool union_(int a, int b)
{
  int tataA = GetFather(a);
  int tataB = GetFather(b);

  if (tataA == tataB)
    return false;

  if (h[tataA] == h[tataB])
  {
    h[tataA]++;
    tata[tataB] = tataA;
  }
  else if (h[tataA] > h[tataB])
  {
    tata[tataB] = tataA;
  }
  else
  {
    tata[tataA] = tataB;
  }

  return true;
}

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

  in >> n >> m;

  init();

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

  sort(muchii + 1, muchii + 1 + m);

  int sol = 0;

  for (int i = 1; i <= m && muchiiSol.size() < n - 1; ++i)
  {
    if (union_(muchii[i].x, muchii[i].y))
    {
      sol += muchii[i].cost;
      muchiiSol.emplace_back(i);
    }
  }

  out << sol << '\n';
  out << muchiiSol.size() << '\n';
  for (int i = 0; i < muchiiSol.size(); ++i)
  {
    out << muchii[muchiiSol[i]].x << ' ' << muchii[muchiiSol[i]].y << '\n';
  }

  return 0;
}