#include <cstdio>
#include <algorithm>
using namespace std;

long i,n,s,m,x,nrm;

struct ab{
    long x,y,c;
}mc[400002],sav[200002];
struct multime{
    long nr,ant;
}h[200002];

long comp(ab a,ab b)
{
    return a.c<b.c;
}

long rad(long nod,long &lg)
{
    if (h[nod].ant!=-1)
    {
        lg++;
        return rad(h[nod].ant,lg);
    }
    else
        return nod;
}

long update(long x,long y)
{
    long rx,ry,lgx=1,lgy=1;
    rx=rad(x,lgx);
    ry=rad(y,lgy);
    if (lgx<lgy)
        h[rx].ant = ry;
    else
        h[ry].ant = rx;
}

long query(long x,long y)
{
    long sav,rx,ry,lgx=1,lgy=1;
    rx=rad(x,lgx);
    ry=rad(y,lgy);
    if (h[rx].nr==h[ry].nr)
    {
         if (lgx<lgy)
        {
            while (x!=-1)
            {
                sav=h[x].ant;
                if (x!=ry)
                    h[x].ant=ry;
                x=sav;
            }
        }
        else
        {
            while (y!=-1)
            {
                sav=h[y].ant;
                if (y!=rx)
                h[y].ant=rx;
                y=sav;
            }
        }
        return 1;
    }
    return 0;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%ld%ld",&n,&m);
    for (i=1;i<=n;i++)
    {
        h[i].nr=i;
        h[i].ant=-1;
    }
    for (i=1;i<=m;i++)
        scanf("%ld%ld%ld",&mc[i].x,&mc[i].y,&mc[i].c);
    sort(mc+1,mc+m+1,comp);
    nrm=0;
    x=0;
    while (nrm!=n-1)
    {
        x++;
        if (query(mc[x].x,mc[x].y)==0)
        {
            update(mc[x].x,mc[x].y);
            s+=mc[x].c;
            nrm++;
            sav[nrm]=mc[x];
        }
    }
    printf("%ld\n%ld\n",s,n-1);
    for(i=1;i<=n-1;i++)
        printf("%ld %ld\n",sav[i].x,sav[i].y);

    return 0;
}