#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAXM 400000

struct muchii{
  int noda, nodb, cost;
};
muchii v[MAXM], out[MAXM];
int sef[MAXM];

bool cmp(muchii a, muchii b){
  if(a.cost < b.cost){
    return true;
  }else{
    return false;
  }
}
int findsef(int i){
  if(sef[i] != -1){
    return sef[i] = findsef(sef[i]);
  }else{
    return i;
  }
}
void unite(int i, int j){
  i = findsef(i);
  j = findsef(j);
  sef[i] = j;
}

int main()
{
    FILE *fin, *fout;
    int i, n, m, s, j;
    fin = fopen("apm.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for(i = 0; i < m; i++){
      fscanf(fin, "%d%d%d", &v[i].noda, &v[i].nodb, &v[i].cost);
      sef[i] = -1;
      v[i].noda--;
      v[i].nodb--;
    }
    fclose(fin);
    sort(v, v + m, cmp);
    s = 0;
    j = 0;
    for(i = 0; i < m; i++){
      if(findsef(v[i].noda) != findsef(v[i].nodb)){
        s += v[i].cost;
        unite(v[i].noda, v[i].nodb);
        out[j] = v[i];
        j++;
      }
    }
    fout = fopen("apm.out", "w");
    fprintf(fout, "%d\n%d\n", s, j);
    for(i = 0; i < j; i++){
      fprintf(fout, "%d %d\n", out[i].noda + 1, out[i].nodb + 1);
    }
    fclose(fout);
    return 0;
}