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

using namespace std;

#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();

bool cmp ( int b, int c){
    return ( a[b].z < a[c].z);
}

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

int cn, i, j, k, u = 0, r;
char rezidual[100];

    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;
/*
                itoa(a[r].x, rezidual, 10);
                strcat(sol, rezidual);

                itoa(a[r].y, rezidual, 10);
                sol[strlen(sol)] = ' '; sol[strlen(sol)+1] = '\0';
                strcat(sol, rezidual);
                sol[strlen(sol)] = '\n'; sol[strlen(sol)+1] = '\0';
*/
                tata[i] = j;

                for (k = a[r].x; tata[k] != 0; k = tata[k])
                    if (k != j) tata[k] = j;
                for (k = a[r].y; tata[k] != 0; k = tata[k])
                    if (k != j) tata[k] = j;
            }
    }
    printf("%d\n%d\n", s, u);
//    printf("%s", sol);
    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;
    }
    sort(h+1, h+m+1, cmp );
}