#include <cstdio>
#include <algorithm>

using namespace std;

int sef[200005];

struct muchie
{
    int x,y,c;
}v[400005],sol[200005];

bool cmp(muchie a, muchie b)
{
    if(a.c>b.c)
        return false;
    return true;
}

int sefsup(int bla)
{
    if(sef[bla]==bla)
        return bla;
    else
        return sef[bla]=sefsup(sef[bla]);
}
void unire(int bla1, int bla2)
{
    int sefs1=sefsup(bla1),sefs2=sefsup(bla2);
    sef[sefs1]=sefs2;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,i,cost=0,nrsol=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&v[i].x, &v[i].y, &v[i].c);
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=n;i++)
        sef[i]=i;
    for(i=1;i<=m;i++)
    {
        if(sefsup(v[i].x)!=sefsup(v[i].y))
        {
            unire(v[i].x,v[i].y);
            cost+=v[i].c;
            sol[++nrsol]=v[i];
        }
    }
    printf("%d\n%d\n",cost,n-1);
    for(i=1;i<=n-1;i++)
        printf("%d %d\n",sol[i].x, sol[i].y);
    return 0;
}