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

using namespace std;

#define NMAX 200000

struct edge {
  int from;
  int to;
  int cost;
};

struct rasp{
  int from;
  int to;
};

struct edge v[NMAX+1];
int sef[NMAX+1];
struct rasp raspuns[NMAX+1];

int find(int x){
  if(sef[x]==x){
    return x;
  }
  sef[x]=find(sef[x]);
  return sef[x];
}

void unite(int x,int y){
  sef[find(x)]=find(y);
}

bool comp(edge a,edge b){
  return(a.cost<b.cost);
}

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

  int n,m,x,y,c,i,cost,muchii;
  fscanf(fin,"%d%d",&n,&m);
  for(i=0;i<m;i++){
    fscanf(fin,"%d%d%d",&x,&y,&c);
    v[i].from=x;
    v[i].to=y;
    v[i].cost=c;
  }
  for(i=0;i<n;i++){
    sef[i]=i;///la inceput fiecare nod e intr-o componenta diferita
  }
  std::sort(v,v+m,comp);
  cost=0;
  muchii=0;
  for(i=0;i<m;i++){
    if(find(v[i].from)!=find(v[i].to)){ ///unim comp
      cost+=v[i].cost;
      muchii++;
      raspuns[i].from=v[i].from;
      raspuns[i].to=v[i].to;
      unite(v[i].from,v[i].to);
    }
  }
  fprintf(fout,"%d\n%d\n",cost,muchii);
  for(i=0;i<muchii;i++){
    fprintf(fout,"%d %d\n",raspuns[i].from,raspuns[i].to);
  }

  fclose(fin);
  fclose(fout);
  return 0;
}