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

#define maxm 400000
#define maxn 200000

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

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

muchie v[maxn];
int n,m,tt[maxn],rg[maxn],sel[maxn],cost;

int functie(muchie a,muchie b){
  return a.c<b.c;
}

void initializare(){
  int i;
  fscanf(in,"%d%d",&n,&m);
  i=m+1;
  while(--i) //printf("(%d)",i);
        fscanf(in,"%d%d%d",&v[i].a,&v[i].b,&v[i].c);
  for(i=1;i<=n;i++)tt[i]=i,rg[i]=1;
    sort(v+1,v+m+1,functie);
}

int find (int x){
  int r,y;
  for(r=x;tt[r]!=r;r=tt[r]);
  for(;tt[x]!=x;){
    y=tt[x];
    tt[x]=r;
    x=y;
  }
  return r;
}

void unite(int x,int y){
  if(rg[x]>rg[y]) tt[y]=x;
  else tt[x]=y;
  if(rg[x]==rg[y]) rg[y]++;
}

void kruskal(){
  int nrsel=0,i,a,b,c;
  for(i=1;nrsel<n-1;i++){
    a=v[i].a;
    b=v[i].b;
    c=v[i].c;
    if(find(a)!=find(b)){
      sel[++nrsel]=i;
      cost+=c;
      unite(a,b);
    }
  }
  
}


int main(){
  initializare();
    kruskal();
  fprintf(out,"%d\n%d\n",cost,n-1);
   for(int i=1;i<n;i++)fprintf(out,"%d %d\n",v[sel[i]].a,v[sel[i]].b); 
   // for(int i=1;i<=m;i++)fprintf(out,"%d %d\n",v[i].a,v[i].b); 
  fclose(in);
  fclose(out);
  return 0;
}