#include<stdio.h>
#include<stdlib.h>

#define N 200003
#define M 400004

int n, m, h[M], s, tata[N], sol[N];

typedef struct muchii{int x, y, z;} muc;
muc a[M];


void citire();

int comp ( const void *b, const void *c){
    return ( a[*(int*)b].z - a[*(int*)c].z);
}

int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();

int cn, i, j, k, u = 0, r;

    for (cn = 1; cn <= m; cn++){
        r = h[cn];
            for (i = a[r].x; tata[i] != 0; i = tata[i]);
            for (j = a[r].y; tata[j] != 0; j = tata[j]);

            if (i != j){
                s += a[r].z; sol[++u] = r;
                tata[j] = i;

                for (k = a[r].x; tata[k] != 0; k = tata[k])
                    if (k != i) tata[k] = i;
                for (k = a[r].y; tata[k] != 0; k = tata[k])
                    if (k != i) tata[k] = i;
            }
    }
    printf("%d\n%d\n", s, u);
    for (i = 1; i <= u; i++)
        printf("%d %d\n",a[sol[i]].x, a[sol[i]].y);

    return 0;
}

void citire(){
int i;
    scanf("%d %d", &n, &m);
    for (i = 1; i <= m; i++){
        scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
        h[i] = i;
    }
    qsort(h+1, m, sizeof(int), comp );
 /*   for (i = 1; i <= m; i++)
        printf("%d %d %d\n", a[h[i]].x, a[h[i]].y, a[h[i]].z);
*/
}