#include<cstdio>
#include<algorithm>

using namespace std;

int t[400010],h[400010];

struct OLHA {
    int x,y,c;
}v[400010];

bool cmp(OLHA a,OLHA b) {
    return a.c<b.c;
}

int findset(int x) {
    while (x!=t[x])
        x=t[x];
    return x;
}

bool unionset(int x,int y) {
    int tx,ty;
    tx=findset(x);
    ty=findset(y);
    if (tx==ty)
        return 0;
    if (h[tx]==h[ty]) {
        h[tx]++;
        t[ty]=tx;
    }
    else
        if (h[tx]<h[ty])
            t[tx]=ty;
        else
            t[ty]=tx;
    return 1;
}

int main()
{
    int n,m,i,tx,ty,tc,cost=0;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d", &n, &m);
    for (i=1;i<=m;i++) {
        scanf("%d%d%d", &tx, &ty, &tc);
        v[i].x=tx;
        v[i].y=ty;
        v[i].c=tc;
    }
    sort(v+1,v+m+1,cmp);
    for (i=1;i<=n;i++)
        t[i]=i,h[i]=1;
    for (i=1;i<=m;i++) {
        if (unionset(v[i].x,v[i].y)==1)
            cost+=v[i].c;
        else
            v[i].x=v[i].y=0;
    }
    printf("%d\n%d\n", cost, n-1);
    for (i=1;i<=m;i++)
        if (v[i].x!=0)
            printf("%d %d\n", v[i].y, v[i].x);
    return 0;
}