#include <fstream>
#include <iostream>
#include <stdlib.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int t[200001],h[200001],S;
typedef struct muchie
{
    int valoare;
    int a;
    int b;
};
int cmp(const void *a,const void *b)
{
   struct muchie *ca=(struct muchie *)a;
   struct muchie *cb=(struct muchie *)b;
   return ca->valoare-cb->valoare;
}
int tata(int x)
{
    while(t[x]!=x)
        x=t[x];
    return x;

}

int main()
{
    int n,m;
    f>>n>>m;
    struct muchie v[m+1],sol[n];
    for(int i=1;i<=m;i++)
        f>>v[i].a>>v[i].b>>v[i].valoare;
    qsort(v+1,m,sizeof(struct muchie),cmp);
    for(int i=1;i<=n;i++)
        {t[i]=i;
        h[i]=0;
        }

    int k=0;
    for(int i=1;i<=m;i++)
    {
        if(k==n-1)
            break;
        else
        {  int x=tata(v[i].a);
           int y=tata(v[i].b);
            if(x!=y)
              {
                  k++;
                  if(h[x]>h[y])
                    t[y]=x;
                  else if(h[x]==h[y])
                    {
                      h[x]++;
                      t[y]=x;
                     }
                    else
                     t[x]=y;
                  sol[k].a=v[i].a;
                  sol[k].b=v[i].b;
                  sol[k].valoare=v[i].valoare;
                  S=S+sol[k].valoare;

              }

        }
    }
    g<<S<<'\n';
    g<<k<<'\n';
    for(int i=1;i<=k;i++)
        g<<sol[i].a<<' '<<sol[i].b<<'\n';
    return 0;
}