#include <iostream>
#include <fstream>
#define Mmax 400005
#define Nmax 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,nr;
int CompC[Nmax];
struct muchie
{
    int x,y,cost;
};
muchie a[Mmax],sol[Nmax];
void Citire ()
{
    int i,x,y,cost;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        a[i].x=x;
        a[i].y=y;
        a[i].cost=cost;
    }
}
int Pivotare (int s,int d)
{
    muchie aux;
    int i,j,ok=1;
    i=s;j=d;
    while (i<j)
    {
        if (a[i].cost>a[j].cost)
        {
            aux=a[i];
            a[i]=a[j];
            a[j]=aux;
            ok*=-1;
        }
        if (ok==1) j--;
        else i++;
    }
    return i;
}
void QS (int s,int d)
{
    int p;
    if (s<d)
    {
        p=Pivotare(s,d);
        QS(s,p-1);
        QS(p+1,d);
    }
}

void APM ()
{
    int i,k,costminim=0,c1,c2,j;
    for (i=1;i<=n;i++)
        CompC[i]=i;
    k=1;
    for (i=1;i<n;i++)
    {
            while (CompC[a[k].x]==CompC[a[k].y]) k++;
            costminim+=a[k].cost;
            c1=CompC[a[k].x];
            c2=CompC[a[k].y];
            for (j=1;j<=n;j++)
                if (CompC[j]==c1) CompC[j]=c2;
            nr++;
            sol[nr].x=a[k].x;
            sol[nr].y=a[k].y;
    }
    fout<<costminim<<"\n"<<n-1<<"\n";
    for (i=1;i<=nr;i++)
        fout<<sol[i].x<<" "<<sol[i].y<<"\n";
}
int main()
{int i;
    Citire();
    QS(1,m);
    /*for (i=1;i<=m;i++)
        fout<<a[i].x<<" "<<a[i].y<<" "<<a[i].cost<<"\n";
    */
    APM();
    return 0;
}