#include <fstream>
#include <algorithm>

#define NMAX 200000
#define MMAX 400000

using namespace std;

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

struct type_muchie{
  int a, b, cost;
};

bool cmp(type_muchie x, type_muchie y) {
  return x.cost < y.cost;
}

type_muchie v[MMAX + 1];

int muchieAfis[NMAX * 2 + 1];

int daddy[NMAX + 1];

int getDaddy(int x) {
  if(daddy[x] == 0)
    return x;
  else {
    daddy[x] = getDaddy(daddy[x]);
    return daddy[x];
  }
}

void joinDaddy(int x, int y) {
  daddy[getDaddy(x)] = getDaddy(y);
}

int main() {
  int n, m;
  long long cost = 0;
  cin>>n>>m;
  for(int i = 1; i <= m; i++) {
    cin>>v[i].a>>v[i].b>>v[i].cost;
  }
  sort(v + 1, v + m + 1, cmp);
  int k = 0;
  for(int i = 1; i <= m; i++) {
    if(getDaddy(v[i].a) != getDaddy(v[i].b)) {
      k++;
      cost += v[i].cost;
      joinDaddy(v[i].a, v[i].b);
      muchieAfis[k * 2 - 1] = v[i].a;
      muchieAfis[k * 2] = v[i].b;
    }
  }
  cout<<cost<<"\n";
  cout<<k<<"\n";
  for(int i = 1; i <= k; i++) {
    cout<<muchieAfis[i * 2 - 1]<<" "<<muchieAfis[i * 2]<<"\n";
  }
  return 0;
}