#include <fstream>
#include<vector>
#include<cstdlib>
using namespace std;
struct muchii
{
    int a,b,c;
    bool ales;
};
vector <muchii> l;
void quickSort(int left, int right) {

      int i = left, j = right;
      muchii tmp;
      muchii pivot = l[(left + right) / 2];
      while (i <= j)
    {
            while (l[i].c < pivot.c)
                  i++;
            while (l[j].c > pivot.c)
                  j--;
            if (i <= j)
            {
                  tmp = l[i];
                  l[i] = l[j];
                  l[j] = tmp;
                  i++;
                  j--;
            }
      };
      if (left < j)
            quickSort(left, j);

      if (i < right)
            quickSort(i, right);

}
/*int PARTITION(int p,int r)
 {
        muchii temp,temp1;
        int x=l[r].c;
        int i=p-1;
        for(int j=p;j<=r-1;j++)
        {
            if(l[j].c<=x)
            {

                i=i+1;
                temp=l[i];
                l[i]=l[j];
                l[j]=temp;
            }
        }
        temp1=l[i+1];
        l[i+1]=l[r];
        l[r]=temp1;
        return i+1;
  }
   int R_PARTITION(int p,int r)
 {
        int i=p+rand()%(r-p+1);
        muchii temp;
        temp=l[r];
        l[r]=l[i];
        l[i]=temp;
        return PARTITION(p,r);
  }
  void R_QUICKSORT(int p,int r)
    {
        int q;
        if(p<r)
        {
         q=R_PARTITION(p,r);
         R_QUICKSORT(p,q-1);
         R_QUICKSORT(q+1,r);
        }
    }*/
struct vizitator
{
    int nr, v;
};
int main()
{
    int n,m;
    ifstream f("apm.in");
    ofstream g("apm.out");
    vector<vizitator> viz;
    int x,y,C;
    f>>n>>m;
    for(int i=0;i<m;i++)
    {
        f>>x>>y>>C;
        muchii M;
        M.a=x;
        M.b=y;
        M.c=C;
        M.ales=false;
        l.push_back(M);
    }
    quickSort(0,m-1);
    vizitator aux;
    aux.nr=0;
    aux.v=-1;
    viz.resize(n,aux);
    int nr=1;
    long cost=0;
    for(int i=0;i<m;i++)
    {
        if(viz[l[i].a].v==-1&&viz[l[i].b].v==-1)
        {
            viz[l[i].a].v=nr;
            viz[l[i].b].v=nr;
            nr++;
            viz[l[i].a].nr=2;
            viz[l[i].b].nr=2;
            l[i].ales=true;
            cost+=l[i].c;
        }
        else
            if(viz[l[i].a].v==-1&&viz[l[i].b].v!=-1)
        {
            l[i].ales=true;
            cost+=l[i].c;
            int aux=viz[l[i].b].v;
            for(int j=1;j<=n;j++)
            {
                if(viz[j].v==aux)
                    viz[j].nr++;
            }
            viz[l[i].a].v=aux;
            viz[l[i].a].nr=viz[l[i].b].nr;
        }
        else
        if(viz[l[i].b].v==-1&&viz[l[i].a].v!=-1)
        {
            l[i].ales=true;
            cost+=l[i].c;
            int aux=viz[l[i].a].v;
            for(int j=1;j<=n;j++)
            {
                if(viz[j].v==aux)
                    viz[j].nr++;
            }
            viz[l[i].b].v=aux;
            viz[l[i].b].nr=viz[l[i].a].nr;
        }
        else
        if(viz[l[i].a].v!=viz[l[i].b].v)
        {
            if(viz[l[i].a].nr<viz[l[i].b].nr)
            {
                int aux=viz[l[i].a].v;
                int nr2=viz[l[i].a].nr;
                for(int j=1;j<=n;j++)
                {
                    if(viz[j].v==aux)
                        {
                            viz[j].v=viz[l[i].b].v;
                            viz[j].nr+=nr2;
                        }
                        else
                            if(viz[j].v==viz[l[i].b].v)
                            viz[j].nr+=nr2;
                }
                l[i].ales=true;
                cost+=l[i].c;
            }
            else
            {
                int aux=viz[l[i].b].v;
                int nr2=viz[l[i].b].nr;
                for(int j=1;j<=n;j++)
                {
                    if(viz[j].v==aux)
                        {
                            viz[j].v=viz[l[i].a].v;
                            viz[j].nr+=nr2;
                        }
                        else
                            if(viz[j].v==viz[l[i].a].v)
                            viz[j].nr+=nr2;
                }
                l[i].ales=true;
                cost+=l[i].c;
            }
        }
    }
    g<<cost<<"\n"<<n-1<<"\n";
    for(int i=0;i<m;i++)
    {
        if(l[i].ales==true)
            g<<l[i].b<<" "<<l[i].a<<"\n";
    }
    f.close();
    g.close();
    return 0;
}