#include <fstream>
#include<vector>
#include<cstdlib>
using namespace std;
struct muchii
{
    int a,b,c;
    bool ales;
};
int PARTITION(vector <muchii> a,int p,int r)
 {
        muchii temp,temp1;
        int x=a[r].c;
        int i=p-1;
        for(int j=p;j<=r-1;j++)
        {
            if(a[j].c<=x)
            {

                i=i+1;
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
        temp1=a[i+1];
        a[i+1]=a[r];
        a[r]=temp1;
        return i+1;
  }
   int R_PARTITION(vector <muchii> a,int p,int r)
 {
        int i=p+rand()%(r-p+1);
        muchii temp;
        temp=a[r];
        a[r]=a[i];
        a[i]=temp;
        return PARTITION(a,p,r);
  }
  void R_QUICKSORT(vector<muchii> a,int p,int r)
    {
        int q;
        if(p<r)
        {
         q=R_PARTITION(a,p,r);
         R_QUICKSORT(a,p,q-1);
         R_QUICKSORT(a,q+1,r);
        }
    }
struct vizitator
{
    int nr, v;
};
int main()
{
    int n,m;
    ifstream f("apm.in");
    ofstream g("apm.out");
    vector <muchii> l;
    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);
    }
    R_QUICKSORT(l,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"<<nr-1<<"\n";
    for(int i=0;i<m;i++)
    {
        if(l[i].ales==true)
            g<<l[i].a<<" "<<l[i].b<<"\n";
    }
    f.close();
    g.close();
    return 0;
}