#include <fstream>
#include <vector>

using namespace std;

fstream f("apm.in",ios::in);
fstream g("apm.out",ios::out);

const int Mmax=400005,nmax=200005;

int n,m,i,j,x[Mmax],y[Mmax],c[Mmax],a[nmax],r[nmax],xx,yy,pus[Mmax],nr;
long long suma;
void citire()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>x[i]>>y[i]>>c[i];
        /*a[x[i]].push_back(make_pair(y[i],c[i]));
        a[y[i]].push_back(make_pair(x[i],c[i]));*/
    }
}

 void quickSort(int left, int right)
 {
  int i = left, j = right;
  int tmp;
  int pivot = c[(left + right) / 2];

  /* partition */
  while (i <= j) {
        while (c[i] < pivot)
              i++;
        while (c[j] > pivot)
              j--;
        if (i <= j) {
              tmp = c[i];
              c[i] = c[j];
              c[j] = tmp;
              tmp=x[i];
              x[i]=x[j];
              x[j]=tmp;
              tmp=y[i];
              y[i]=y[j];
              y[j]=tmp;
              i++;
              j--;
    }
}
/* recursion */
if (left < j)
    quickSort(left, j);
if (i < right)
        quickSort(i, right);
}


int find(int nod)
{
    int aux,nc;
    nc=nod;
    while (nc!=a[nc])
    {
        nc=a[nc];
    }
    while (nod!=a[nod])
    {
        aux=a[nod];
        a[nod]=nc;
        nod=aux;
    }
    return nc;
}

void uneste(int n1,int n2)
{
    if (r[n1]>r[n2]) a[n2]=n1;
            else a[n1]=n2;
    if (r[n1]==r[n2]) r[n2]++;
}


int main()
{
    citire();
    quickSort(1,m);
    for (i=1;i<=n;i++)
    {
        a[i]=i;
        r[i]=1;
    }
    suma=0;
    nr=0;
    for (i=1;i<=m;i++)
    {
        xx=find(x[i]);yy=find(y[i]);
        if (xx!=yy)
            {
                uneste(xx,yy);
                suma=suma+c[i];
                pus[i]=1;
                nr++;
            }
    }
    g<<suma<<'\n';
    g<<nr<<'\n';
    for (i=1;i<=m;i++) if (pus[i]) g<<x[i]<<" "<<y[i]<<'\n';
    return 0;
}