#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 70
#define MAX_M 400000
struct muchii {
  int a,b,cost;
};
int n,m;
muchii v[MAX_M];
int index[MAX_N];
vector <pair<int,int>> rez;
bool cmp(const muchii& a,const muchii& b){
  return a.cost<b.cost;
}
void init(int n){
  for(int i=0;i<n;i++){
    index[i]=i;
  }
}
int find(int x){
  if(x==index[x])
    return x;
  return index[x]=find(index[x]);
}

void unite(int x,int y){
  int setX,setY;

  setX=find(x);
  setY=find(y);
  if(setX!=setY){
    if(rand()&1){
      index[setX]=setY;
    }else{
      index[setY]=setX;
    }
  }
}
int main(){
  FILE *fin,*fout;
  int i,sum;
  fin=fopen("apm.in","r");
  fout=fopen("apm.out","w");
  fscanf(fin,"%d%d",&n,&m);
  init(n);
  for(i=0;i<m;i++){
    fscanf(fin,"%d%d%d",&v[i].a,&v[i].b,&v[i].cost);
    v[i].a--;
    v[i].b--;
  }

  sort(v,v+m,cmp);

  sum=0;
  for(i=0;i<m;i++){
    if(find(v[i].a)!=find(v[i].b)){
      sum+=v[i].cost;
      unite(v[i].a,v[i].b);
      rez.push_back({v[i].a,v[i].b});
    }
  }

  fprintf(fout,"%d\n%d\n",sum,n-1);
  for(auto d:rez){
    fprintf(fout,"%d %d\n",d.first+1,d.second+1);
  }
  fclose(fin);
  fclose(fout);
  return 0;
}