#include <algorithm>
#include <fstream>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int m, n;

struct Muchie
{
  int x = 0, y = 0, cost = 0;
};

vector<Muchie> muchii;
vector<Muchie> arbore_rezultat;
vector<bool> viz;
vector<int> tata, inaltime_subarbore;

void Read()
{
  f >> n >> m;
  viz.resize(n + 1);
  tata.resize(n + 1);
  inaltime_subarbore.resize(n + 1);

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

  for (int i = 0; i < m; i++)
  {
    Muchie muchie;
    f >> muchie.x >> muchie.y >> muchie.cost;
    muchii.push_back(muchie);
  }
}

int Reprezentant(int u)
{
  if (u == tata[u])
    return u;
  return tata[u] = Reprezentant(tata[u]);
}

void Reuneste(int u, int v)
{
  int repr_u, repr_v;
  repr_u = Reprezentant(u);
  repr_v = Reprezentant(v);

  if (inaltime_subarbore[repr_u] > inaltime_subarbore[repr_v])
  {
    tata[repr_v] = repr_u;
  }
  else
  {
    tata[repr_u] = repr_v;
    if (inaltime_subarbore[repr_u] == inaltime_subarbore[repr_v])
      inaltime_subarbore[repr_u]++;
  }
}

void Kruskal()
{
  sort(muchii.begin(), muchii.end(),
       [](Muchie &a, Muchie &b)
       { return a.cost < b.cost; });

  int nr_muchii_arbore = 0;
  for (auto &muchie : muchii)
  {
    if (Reprezentant(muchie.x) != Reprezentant(muchie.y))
    {
      arbore_rezultat.push_back(muchie);
      Reuneste(muchie.x, muchie.y);
      nr_muchii_arbore++;
      if (nr_muchii_arbore == n - 1)
        break;
    }
  }

  int s = 0;
  for (auto &muchie : arbore_rezultat)
    s += muchie.cost;

  g << s << '\n'
    << arbore_rezultat.size() << '\n';

  for (auto muchie : arbore_rezultat)
  {
    g << muchie.x << ' ' << muchie.y << '\n';
  }
}

int main()
{
  Read();
  Kruskal();

  return 0;
}