#include <fstream>
#include <algorithm>
#define MAX 400001

using namespace std;

struct muchie
{
  int st;
  int dr;
  int cost;
}v[MAX];

int daddy[MAX / 2 + 1];

int find_daddy(int nod)
{
  if(daddy[nod] == nod)return nod;
  return nod = find_daddy(daddy[nod]);
}

bool union_find(int nod1, int nod2)
{
  int daddy1 = find_daddy(nod1);
  int daddy2 = find_daddy(nod2);

  if(daddy1 != daddy2)
  {
    daddy[daddy1] = daddy2;
    return true;
  }

  return false;
}

bool cmp(muchie a, muchie b)
{
  if(a.cost < b.cost)return true;
  return false;
}

int main()
{
  int n, m, i, j, costMinim = 0, contor = 0;

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

  fin >> n >> m;

  for(i = 1; i <= m; i++)
  {
    fin >> v[i].st >> v[i].dr >> v[i].cost;
  }

  sort(v + 1, v + m + 1, cmp);

  for(i = 1; i <= n; i++)daddy[i] = i;

  costMinim = contor = 0;

  for(i = 1; contor < n - 1 && i <= m; i++)
  {
    if(union_find(v[i].st, v[i].dr))
    {
      costMinim += v[i].cost;
      contor++;
    }
  }

  for(i = 1; i <= n; i++)daddy[i] = i;

  fout << costMinim << '\n' << n - 1 << '\n';

  costMinim = contor = 0;

  for(i = 1; contor < n - 1 && i <= m; i++)
  {
    if(union_find(v[i].st, v[i].dr))
    {
      fout << v[i].st << " " << v[i].dr << '\n';
      costMinim += v[i].cost;
      contor++;
    }
  }

  fin.close();
  fout.close();

  return 0;
}