#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();
int divide(int p, int q);
void sortare(int p, int q);
void kruskal_greedy();
void afisare();

int main()
{
citire();
sortare(1,m);
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;
}

int divide(int p, int q)
{
    int st=p,dr=q;
    muchie x=mc[p];
    while (st<dr)
    {
        while (st<dr && mc[dr].c>=x.c)   dr--;
            mc[st]=mc[dr];
        while (st<dr && mc[st].c<=x.c)   st++;
            mc[dr]=mc[st];
    }
    mc[st]=x;
    return st;
}

void sortare(int p, int q)
{
    int m=divide(p,q);
    if (m-1>p)  sortare(p,m-1);
    if (m+1<q)  sortare(m+1,q);
}

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';
}