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

using namespace std;

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

struct MUCHIE
{
 int x, y, c;
 bool v;
};

vector<MUCHIE> v(1);
vector<int> t(1), h(1);
MUCHIE temp;
int n, m, x, y, c, vfx, vfy, nrm, cost, i;

bool cmp(MUCHIE a, MUCHIE b)
{
 return a.c < b.c;
}

int varf(int x)
{
 while (x != t[x])
  x = t[x];
 return x;
}

void unire(int x, int y)
{
 if (h[x] < h[y])
  t[x] = y;
 else if (h[y] < h[x])
  t[y] = x;
 else
 {
  t[y] = x;
  ++h[x];
 }
}

int main()
{
 fin >> n >> m;
 for (i = 1; i <= n; ++i)
 {
  t.push_back(i);
  h.push_back(1);
 }
 for (i = 1; i <= m; ++i)
 {
  fin >> x >> y >> c;
  temp.x = x;
  temp.y = y;
  temp.c = c;
  v.push_back(temp);
 }
 sort(v.begin() + 1, v.end(), cmp);
 for (i = 1; i <= m; ++i)
 {
  vfx = varf(v[i].x);
  vfy = varf(v[i].y);
  if (vfx != vfy)
  {
   unire(vfx, vfy);
   v[i].v = true;
   ++nrm;
   cost += v[i].c;
  }
 }
 fout << cost << '\n' << nrm << '\n';
 for (i = 1; i <= m; ++i)
  if (v[i].v)
   fout << v[i].x << ' ' << v[i].y << '\n';
 fin.close();
 fout.close();
 return 0;
}