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

using namespace std;

#define N 200003
#define M 400004

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

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

typedef struct solutie{int x, y;} soll;
soll sol[N];

void citire();

int comp ( 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;

    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].x = a[r].x;
                sol[u].y = a[r].y;
                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);
    for (i = 1; i <= u; i++)
        printf("%d %d\n",sol[i].x, 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, comp );
 /*   for (i = 1; i <= m; i++)
        printf("%d %d %d\n", a[h[i]].x, a[h[i]].y, a[h[i]].z);
*/
}