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

struct edge{
  int x,y,c;
}v[MAXM],sol[MAXM];
int d;

void downheap(int nod){
  int son=nod*2+1,aux;
  if(son+1<d && v[son+1].c<v[son].c)
    son++;
  while(son<d && v[nod].c>v[son].c){
    aux=v[nod].c; v[nod].c=v[son].c; v[son].c=aux;
    aux=v[nod].x; v[nod].x=v[son].x; v[son].x=aux;
    aux=v[nod].y; v[nod].y=v[son].y; v[son].y=aux;
    nod=son;
    son=nod*2+1;
    if(son+1<d && v[son+1].c<v[son].c)
        son++;
  }
}

void heapify(){
  int i;
  for(i=(d-1)/2; i>=0; i--)
    downheap(i);
}

int p[MAXN+1],st[MAXN];

int find(int x){
  int sp=0;
  while(p[x]!=x){
    st[sp++]=x;
    x=p[x];
  }
  for(int i=0; i<sp; i++)
    p[st[i]]=x;
  return x;
}

void Union(int x, int y){
  int m1=find(x);
  int m2=find(y);
  p[m2]=m1;
}

int main(){
  FILE *fin=fopen("apm.in","r");
  FILE *fout=fopen("apm.out","w");
  int n,m,i,apm=0,mapm=0;

  fscanf(fin,"%d%d",&n,&m);
  for(i=0; i<m; i++)
    fscanf(fin,"%d%d%d",&v[i].x,&v[i].y,&v[i].c);
  for(i=1; i<=n; i++)
    p[i]=i;
  d=m;
  heapify();
  while(d){
    if(find(v[0].x)!=find(v[0].y)){
      apm+=v[0].c;
      sol[mapm].x=v[0].x;
      sol[mapm++].y=v[0].y;
      Union(v[0].x,v[0].y);
    }
    v[0].c=v[--d].c;
    v[0].x=v[d].x;
    v[0].y=v[d].y;
    downheap(0);
  }
  fprintf(fout,"%d\n%d\n",apm,mapm);
  for(i=0; i<mapm; i++)
    fprintf(fout,"%d %d\n",sol[i].x,sol[i].y);
  fclose(fin);
  fclose(fout);
  return 0;
}