#include <stdio.h>
#include <stdlib.h>
#define MAXN 200000
#define MAXM 400000

int grnod[MAXN+1];

struct chestie{
  int x, y, c;
} v[MAXM+1], sol[MAXN], aux, piv;

void myqsort(int beg, int end){
  int b=beg, e=end;
  piv=v[beg+rand()%(end-beg+1)];
  while(b<=e){
    while(v[b].c<piv.c)
      ++b;
    while(v[e].c>piv.c)
      --e;
    if(b<=e){
      aux=v[b]; v[b]=v[e]; v[e]=aux;
      ++b; --e;
    }
  }
  if(beg<e)
    myqsort(beg, e);
  if(b<end)
    myqsort(b, end);
}

int submult(int a){
  if(grnod[a]==a)
    return a;
  grnod[a]=submult(grnod[a]);
  return grnod[a];
}

void un(int a, int b){
  grnod[submult(a)]=submult(b);
}

int main()
{
    FILE *fin, *fout;
    int n, m, i, nr, ctot;
    fin=fopen("apm.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=m; i++)
      fscanf(fin, "%d%d%d", &v[i].x, &v[i].y, &v[i].c);
    myqsort(1, m);
    for(i=1; i<=n; i++)
      grnod[i]=i;
    nr=ctot=0;
    for(i=1; i<=m; i++)
      if(submult(v[i].x)!=submult(v[i].y)){
        sol[nr++]=v[i];
        ctot+=v[i].c;
        un(v[i].x, v[i].y);
      }
    fclose(fin);
    fout=fopen("apm.out", "w");
    fprintf(fout, "%d\n%d\n", ctot, n-1);
    for(i=0; i<nr; i++)
      fprintf(fout, "%d %d\n", sol[i].x, sol[i].y);
    return 0;
}