#include <fstream>
#define NMAX 200010
#define MMAX 400010

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie
{
    int x,y,c;
};
muchie mc[MMAX],sol[NMAX];
int n,m,nr=1,cmin;
int c[NMAX];

void citire();
void sortare();
void kruskal_greedy();
void afisare();

int main()
{
citire();
sortare();
kruskal_greedy();
afisare();
return 0;
}

void citire()
{
    int i;
    fin >> n >> m;
    for (i=1;i<=m;i++)
        fin >> mc[i].x >> mc[i].y >> mc[i].c;
    for (i=1;i<=n;i++)
        c[i]=i;
}

void sortare()
{
    int i,ok=1;
    muchie aux;
    while (ok)
    {
        ok=0;
        for (i=1;i<m;i++)
            if (mc[i].c>mc[i+1].c)
            {
                aux=mc[i];   mc[i]=mc[i+1];    mc[i+1]=aux;
                ok=1;
            }
    }
}

void kruskal_greedy()
{
    int i,j,min,max;
    sol[1]=mc[1];    cmin+=mc[1].c;

    if (c[mc[1].x]<c[mc[1].y])
        { min=c[mc[1].x]; max=c[mc[1].y]; }
    else
        { min=c[mc[1].y]; max=c[mc[1].x]; }

    for (j=1;j<=n;j++)
        if (c[j]==max)  c[j]=min;

    for (i=2; i<=m && nr<n-1; i++)
        if (c[mc[i].x]!=c[mc[i].y])
        {
            sol[++nr]=mc[i];    cmin+=mc[i].c;
            if (c[mc[i].x]<c[mc[i].y])
                { min=c[mc[i].x]; max=c[mc[i].y]; }
            else
                { min=c[mc[i].y]; max=c[mc[i].x]; }
            for (j=1;j<=n;j++)
                if (c[j]==max)  c[j]=min;
        }
}

void afisare()
{
    int i;
    fout << cmin << '\n';
    fout << nr << '\n';
    for (i=1;i<=nr;i++)
        fout << sol[i].y << ' ' << sol[i].x << '\n';
}