#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX=200005;
struct VEK
{
    int a, b, l;
};
struct MUCHIE
{
    int x, y;
};
VEK v[2*NMAX];
MUCHIE a[2*NMAX];
int daddy[NMAX], h[NMAX];

bool cmp(VEK x, VEK y)
{
    if (x.l<y.l)
        return 1;
    return 0;
}
int findPAPA(int x)
{
    while(daddy[x]!=x)
        x=daddy[x];
    return x;
}
void UnionSet(int x, int y)
{
    if (h[x]==h[y])
    {
        daddy[findPAPA(y)]=findPAPA(x);
        h[x]++;
    }
    else
        if (h[x]>h[y])
            daddy[findPAPA(y)]=findPAPA(x);
        else
            daddy[findPAPA(x)]=findPAPA(y);
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int n, m, i, s=0, MM=0, x, y;
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++)
        daddy[i]=i, h[i]=1;
    for(i=1; i<=m; i++)
        scanf("%d%d%d", &v[i].a, &v[i].b, &v[i].l);
    sort(v+1, v+1+m, cmp);

    for(i=1; i<=m && MM!=n-1; i++)
    {
        x=v[i].a;
        y=v[i].b;
        if(findPAPA(x)!=findPAPA(y))
        {
            UnionSet(x, y);
            s+=v[i].l;
            MM++;
            a[MM].x=x;
            a[MM].y=y;
        }
    }

    printf("%d\n%d\n", s, MM);
    for(i=1; i<=MM; i++)
        printf("%d %d\n", a[i].x, a[i].y);
    //for(i=1; i<=m; i++)
        //printf("%d %d %d\n", v[i].a, v[i].b, v[i].l);
    return 0;
}