#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 200000
#define MAXM 400000

using namespace std;

struct Edge{
  int a;
  int b;
  int cost;

public:
  int getOther(int id){
    if(id == a)
      return b;
    return a;
  }
};

Edge edges[MAXM];
int p[MAXN], f[MAXM];

void quicksort(int begin, int end){
  int b = begin, e = end, pivot = edges[(b + e) / 2].cost;
  Edge aux;

  while(edges[b].cost < pivot)
    b ++;
  while(edges[e].cost > pivot)
    e --;

  while(b < e){
    aux = edges[b];
    edges[b] = edges[e];
    edges[e] = aux;

    do{
      b ++;
    } while(edges[b].cost < pivot);
    do{
      e --;
    } while(edges[e].cost > pivot);
  }

  if(e > begin)
    quicksort(begin, e);
  if(e + 1 < end)
    quicksort(e + 1, end);
}

int getParent(int id){
  // printf("%d ", id);
  if(p[id] == id)
    return id;

  int parent = getParent(p[id]);
  p[id] = parent;
  return parent;
}

void unite(int x, int y){
  int px = getParent(x);
  int py = getParent(y);

  p[px] = py;
}

int main(){
  int n, i, j, m, a, b, c, s, nr;

  ifstream fin("apm.in");
  fin >> n >> m;
  
  for(i = 0; i < m; i ++){
    fin >> a >> b >> c;
    a --;
    b --;

    edges[i] = {a, b, c};
  }
  fin.close();

  for(i = 0; i < n; i ++){
    p[i] = i;
  }
  quicksort(0, m-1);

  s = 0;
  nr = 0;
  for(i = 0; i < m; i ++){
    if(getParent(edges[i].a) != getParent(edges[i].b)) {
      unite(edges[i].a, edges[i].b);
      s += edges[i].cost;
      nr ++;
      f[i] = 1;
    }
  }
  
  ofstream fout("apm.out");
  fout << s << '\n' << nr << '\n';
  for(i = 0; i < m; i ++)
    if(f[i])
      fout << edges[i].a + 1 << ' ' << edges[i].b + 1 << '\n';
  fout.close();
  return 0;
}