#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;
  while(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);
  fclose(in);
  fclose(out);
  return 0;
}