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

using namespace std;

FILE * fin=fopen("apm.in","r");
FILE * fout=fopen("apm.out","w");

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;
    fscanf (fin, "%d%d", &n, &m);
    for (i=1;i<=m;i++)
        fscanf (fin, "%d%d%d", &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;
    fprintf(fout, "%d\n", cmin);
    fprintf(fout, "%d\n", nr);
    for (i=1;i<=nr;i++)
        fprintf(fout, "%d %d\n", sol[i].y, sol[i].x);
}