#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], nivel[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, w;
char rezidual[100];
     memset(nivel, 1, (n+1)*sizeof(int));

    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;/*
                if (nivel[i] > nivel[j])    tata[j] = i;
                else       tata[i] = j;
                if (nivel[i] == nivel[j]) nivel[j] ++;
            */
            if ( tata[a[r].x] > 0)
                for (k = a[r].x; tata[k] != 0; k = w){
                    w = tata[k];
                    tata[k] = j;
                }
                
                if (tata[a[r].y] > 0)
                for (k = a[r].y; tata[k] != 0; k = w){
                    w = tata[k]; 
                    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 );
}