#include<fstream>

using namespace std;
ifstream f("krustkal.in");
ofstream g("apm.out");
struct muchie{
  int x,y,c;
};
muchie v[400001],a[400001];
int l[200001],m,n,nr=0;
void citire(int &m,int &n){
  f>>n>>m;
  for(int i=1;i<=m;i++)
  f>>v[i].x>>v[i].y>>v[i].c;
}
void sortare(){
  muchie aux;
  for(int i=1;i<=m-1;i++)
  for(int j=i+1;j<=m;j++)
  if(v[i].c>v[j].c){
    aux=v[i];
    v[i]=v[j];
    v[j]=aux;
  }
}

int main(){
  citire(m,n);
  sortare();
  for(int i=1;i<=n;i++)
  l[i]=i;
  int k,i,u,w,ct;
  k=0;
  i=1;
  ct=0;
  while(k<(n-1)){
    if(l[v[i].x]!=l[v[i].y]){
      k++;
      ct=ct+v[i].c;
      u=l[v[i].x];
      w=l[v[i].y];
      nr++;
      a[nr].x=u;
      a[nr].y=w;
      for(int j=1;j<=n;j++)
      if(l[j]==u)
      l[j]=w;
    }
    i++;
  }
  g<<ct<<endl;
  g<<nr<<endl;
  for(i=1;i<=nr;i++)
  g<<a[i].x<<" "<<a[i].y<<endl;
  
  return 0;
}