#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi ("apm.in");
ofstream fo ("apm.out");
struct nod
{
  int nod1,nod2,lng;
} drum[400006];
struct pereche
{
  int nod1,nod2;
} p[400006];
int i,nr_nod,nr_muchii,n1,n2,cost,comp[400006],lg[400006],k,rep1,rep2,sol;
bool cmp (nod el1,nod el2)
{
  return (el1.lng<el2.lng);
}
int reprez(int nod)
{
  while (nod!=comp[nod])
    nod=comp[nod];
  return nod;
}
void unire (int nodA,int nodB)
{
  if (lg[nodA]>lg[nodB])
    {
      comp[nodB]=nodA;
      return;
    }
  if (lg[nodB]>lg[nodA])
  {
    comp[nodA]=nodB;
    return;
  }
  if (lg[nodA]==lg[nodB])
  {
    comp[nodB]=nodA;
    lg[nodA]++;
    return;
  }
}
int main()
{
    fi>>nr_nod>>nr_muchii;
    for (i=1;i<=nr_muchii;i++)
    {
      fi>>n1>>n2>>cost;
      if (n1>n2) swap (n1,n2);
      drum[i].nod1=n1;
      drum[i].nod2=n2;
      drum[i].lng=cost;
    }
    sort (drum+1,drum+nr_muchii+1,cmp);
    for (i=1;i<=nr_nod;i++) comp[i]=i;
    for (i=1;k<nr_nod-1;i++)
    {
      n1=drum[i].nod1;
      n2=drum[i].nod2;
      rep1=reprez(n1);
      rep2=reprez(n2);
      if (rep1!=rep2)
      {
        unire(rep1,rep2);
        sol+=drum[i].lng;
        k++;
        p[k].nod1=n1;
        p[k].nod2=n2;
      }
    }
    fo<<sol<<'\n'<<k<<'\n';
    for (i=1;i<=k;i++)
      fo<<p[i].nod1<<' '<<p[i].nod2<<'\n';
    return 0;
}