#include <bits/stdc++.h>
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 (t[x]!=x)
        x=t[x];
    return x;
}

void unificare(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];
            unificare(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;
}