#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct muchie{
  int x, y, c;
};

muchie e[400002], alese[200001];
int tata[200001], nrniv[200001];

int find(int x){
  if(tata[x] == 0)
    return x;
  return find(tata[x]);
}

void unions(int r1, int r2){
  if(nrniv[r1] < nrniv[r2])
    tata[r1] = r2;
  else if(nrniv[r1] > nrniv[r2])
    tata[r2] = r1;
  else{
    tata[r2] = r1;
    nrniv[r1]++;
  }
}

int cmp(muchie a, muchie b){
  return a.c < b.c;
}

int main()
{
  int n, m, i;
  cin >> n >> m;
  for(i = 1; i <= m; ++i)
    cin >> e[i].x >> e[i].y >> e[i].c;
  sort(&e[1], &e[m + 1], cmp);
  int s = 0, nralese = 0;
  for(i = 1; i <= m && nralese < n - 1; ++i){
    int r1 = find(e[i].x);
    int r2 = find(e[i].y);
    if(r1 != r2){
      nralese++;
      alese[nralese] = e[i];
      s += e[i].c;
      unions(r1, r2);
    }
  }
  cout << s << "\n" << nralese << "\n";
  for(i = 1; i < n; ++i)
    cout << alese[i].y << " " << alese[i].x << "\n";
  return 0;
}