#include<stdio.h>
#include<algorithm>
#include<vector>
#define N 200001
using namespace std;
FILE *in, *out;
struct Graf {
  int n1, n2, cost;
} v[N];
int grup[N];
int sol[N];
int n,m;

void qsort(int begin, int end){
  int inc,sf;
  Graf aux,pivot;
  inc = begin;
  sf = end;
  pivot = v[(inc+sf)/2];
  while (inc <= sf){
    while (v[inc].cost < pivot.cost)
      inc ++;
    while (v[sf].cost > pivot.cost)
      sf --;
    if (inc <= sf){
      aux = v[inc];
      v[inc] = v[sf];
      v[sf] = aux;
      inc ++;sf --;
    }
  }
  if (inc < end)
    qsort (inc,end);
  if (begin < sf)
    qsort (begin,sf);
}

int conex (int nod){
  if (grup[nod] == nod)
    return nod;
  grup[nod] =  conex (grup[nod]);
  return grup[nod];
}

void update (int n1, int n2){
  grup[conex(n2)] = conex(n1);
}

void Kruskal (){
  qsort (1,m);

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

  int k, ind, minim;
  k = 0;ind = 0; minim = 0;
  while (k<n-1){
    ind ++;
    if (conex(v[ind].n1) != conex(v[ind].n2) ) {// nu formeaza ciclu
      minim += v[ind].cost;
      update (v[ind].n1,v[ind].n2);
      sol[++k] = ind;
    }
  }

  //afis
  fprintf (out,"%d\n",minim);
  fprintf (out,"%d\n",k);
  for (int i=1;i<n;i++)
    fprintf (out,"%d %d\n",v[sol[i]].n1,v[sol[i]].n2);

}

int main (){
  in = fopen ("apm.in","r");
  out = fopen ("apm.out","w");
  int i,n1,n2,cost;
  fscanf(in,"%d%d",&n,&m);
  for (i=1;i<=m;i++){
    fscanf(in,"%d%d%d",&v[i].n1,&v[i].n2,&v[i].cost);
  }

  Kruskal ();

  fclose (in);
  fclose (out);
  return 0;
}