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

struct punct
{
    int x, y, c;
}u[200002], sol[200002];

int n, m, k, i, ct, j, p[200002], t[200002];

bool cmp(punct x, punct y)
{
    return (x.c<y.c);
}

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

void unifica(int x, int y)
{
    if (p[x]<p[y]) t[x]=y;
    if (p[x]>p[y]) t[y]=x;
    if (p[x]==p[y]){
        t[y]=x;
        p[x]++;
    }
}

int main ()
{

    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", &u[i].x, &u[i].y, &u[i].c);
        t[i]=i;
    }


    sort(u+1, u+m+1, cmp);

    i=1;
    while (k<n-1){
        int rx=root(u[i].x);
        int ry=root(u[i].y);
        if (rx!=ry){
            k++;
            ct+=u[i].c;
            sol[k]=u[i];
            unifica(rx, ry);
        }
        i++;
    }

    printf("%d\n%d\n", ct, k);
    for (i=1; i<=k; i++) printf("%d %d\n", sol[i].x, sol[i].y);
    return 0;
}