#include <stdio.h>
using namespace std;
#include <algorithm>

FILE *f=fopen("apm.in","r"),*g=fopen("apm.out","w");

struct muchie{
  int a,b,cost;
};

muchie gr[400001];
int v[200001],c[200001];
int n,m,costul;

void initializare(){
  int i;
  fscanf(f,"%d%d",&n,&m);
  for(i=1;i<=m;i++)
    fscanf(f,"%d%d%d",&gr[i].a,&gr[i].b,&gr[i].cost);
  for(i=1;i<=n;i++ )c[i]=i;
 
}

int functie(muchie x,muchie y){
  return x.cost<y.cost;
}

void afisare(){
  int i;
  fprintf(g,"%d\n%d\n",costul,n-1);
  for(i=1;i<=n-1;i++){
    fprintf(g,"%d %d \n",gr[v[i]].a,gr[v[i]].b);
  }
}
int main(){
  int i,j,min,max,nrsel;
  initializare();
  sort(gr+1,gr+m+1,functie);
  nrsel=0;
  for(i=1;nrsel<n-1;i++)
    if(c[gr[i].a]!=c[gr[i].b]){
      v[++nrsel]=i;
      costul+=gr[i].cost;
      if(c[gr[i].a]<c[gr[i].b]){
	min=c[gr[i].a];
	max=c[gr[i].b];
      }
      else{
	min=c[gr[i].b];
	max=c[gr[i].a];
      }
      for(j=1;j<=n;j++)
	if(c[j]==max)c[j]=min;
    }
  afisare();
  fclose(f);
  fclose(g);
  return 0;
}