#include <fstream>
#include<vector>
#include<cstdlib>
using namespace std;
struct muchii
{
    int a,b,c;
    bool ales;
};
vector <muchii> l;
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.a=l[i].a;
                l[i].a=l[j].a;
                l[j].a=temp.a;
                temp.b=l[i].b;
                l[i].b=l[j].b;
                l[j].b=temp.b;
                temp.c=l[i].c;
                l[i].c=l[j].c;
                l[j].c=temp.c;
                temp.ales=l[i].ales;
                l[i].ales=l[j].ales;
                l[j].ales=temp.ales;
            }
        }
        temp1.a=l[i+1].a;
        l[i+1].a=l[r].a;
        l[r].a=temp1.a;
        temp1.b=l[i+1].b;
        l[i+1].b=l[r].b;
        l[r].b=temp1.b;
        temp1.c=l[i+1].c;
        l[i+1].c=l[r].c;
        l[r].c=temp1.c;
        temp1.ales=l[i+1].ales;
        l[i+1].ales=l[r].ales;
        l[r].ales=temp1.ales;
        return i+1;
  }
   int R_PARTITION(int p,int r)
 {
        int i=p+rand()%(r-p+1);
        muchii temp;
        temp.a=l[r].a;
        l[r].a=l[i].a;
        l[i].a=temp.a;
        temp.b=l[r].b;
        l[r].b=l[i].b;
        l[i].b=temp.b;
        temp.c=l[r].c;
        l[r].c=l[i].c;
        l[i].c=temp.c;
        temp.ales=l[r].ales;
        l[r].ales=l[i].ales;
        l[i].ales=temp.ales;
        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);
    }
    R_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;
}