#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
std::ifstream fin("apm.in");
std::ofstream fout("apm.out");

struct edge
{
  int x, y,w;
};

struct Comp: std::binary_function<edge,edge,bool>
{
  bool operator() ( edge e1, edge e2)
  {
    return e1.w<e2.w;
  }
};
edge v[400060];
int id[200050];
int siz[200050];
std::vector<edge> rez;
int n,m;
int sum;

int root(int x)
{
  while(id[x]!=x)
  {
    id[x]=id[id[x]];
    x=id[x];
  }
  return x;
}

bool unite(int x, int y)
{
  x= root(x);
  y = root(y);
  bool t = (x!=y);
  if(t)
  {
    if(siz[x]<siz[y])
    {
      siz[y]+=siz[x];
      id[x]=y;
    }
    else
    {
      siz[x]+=siz[y];
      id[y]=x;
    }
  }
  return t;
}

void write()
{
  for(int i=1;i<=n;i++)
    std::cout<<root(i)<<" ";
  std::cout<<"\n";
}

int main()
{
  fin>>n>>m;
  for(int i=1;i<=n;i++)
    id[i]=i;
  for(int i=0;i<m;i++)
  {
    int j,k,o;
    fin>>j>>k>>o;
    v[i]={j,k,o};
  }
  std::sort(v,v+m,Comp());
  //for(int i=0;i<m;i++)
   // std::cout<<v[i].x<<" "<<v[i].y<<" "<<v[i].w<<"\n";
  rez.push_back(v[0]);
  unite(v[0].x,v[0].y);
  sum+=v[0].w;
  for(int i=1;i<m;i++)
  {
  //  write();
    edge elem = v[i];
    //vis[elem.x]=true;
   // vis[elem.y]=true;
    if(unite(elem.x,elem.y))
    {
      rez.push_back(elem);
      sum+=elem.w;
    }
  //  std::cout<<"\n"<<sum<<"\n";
  }
  fout<<sum<<"\n"<<n-1<<"\n";
  for(int i=0;i<n-1;i++)
    fout<<rez[i].x<<" "<<rez[i].y<<"\n";
}