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

using namespace std;

struct muchie
{
   int x, y, c;
   friend bool operator <(muchie p1, muchie p2)
   {
        return p1.c < p2.c;
   }
};

vector<muchie> v;
int t[200002], n, costmin;
int a[200002], b[200002], dim;

int Radacina(int i)
{
    int k;
    k = i;
    while (t[k] > 0)
        k = t[k];
    while (t[i] > 0)
    {
        t[i] = k;
        i = t[i];
    }
    return i;
}

void Unifica(int i, int j)
{
    t[i] += t[j];
    t[j] = i;
}


void Citire()
{
  int i, m, rx, ry, cost;
  unsigned int k;
  muchie p;
  ifstream f("apm.in");
  f >> n >> m;
  for (i = 0; i < m; i++)
  {
    f >> p.x >> p.y >> p.c;
    v.push_back(p);
  }
  f.close();

  sort(v.begin(), v.end(), less<muchie>());

  for (i = 1; i <= n; i++)
        t[i] = -1;
  for (k = 0; k < v.size(); k++)
    {
        p = v[k];
        cost = p.c;
        rx = Radacina(p.x);
        ry = Radacina(p.y);
        if (rx != ry)
        {
            costmin += cost;
            dim++;
            a[dim] = p.x;
            b[dim] = p.y;
            Unifica(rx, ry);
        }
    }
}

void Afisare()
{
    ofstream fout("apm.out");
    fout << costmin << "\n" << dim << "\n";
    for (int i = 1; i <= dim ; i++)
        fout << a[i] << " " << b[i] << "\n";
    fout.close();
}

int main()
{
    Citire();
    Afisare();
    return 0;
}