#include <cstdio>
#include <cstring>
#include <algorithm>
#define x first
#define y second.first
#define z second.second
#define DIM 800010
using namespace std;

pair <int, pair<int, int> > V[DIM];
int N, M, K, X, Y, Z, cost, W[DIM], T[DIM][3];

int Rad(int x){
    int r = x;
    while(W[r] > 0)
        r = W[r];
    x = r;
    while(W[r] > 0){
        int aux = W[r];
        W[r] = x;
        r = aux;
    }
    return x;
}

int main(){

    freopen("apm.in" ,"r", stdin );
    freopen("apm.out","w", stdout);

    scanf("%d %d", &N, &M);

    for(int i = 1; i <= M; i ++){
        scanf("%d %d %d", &Y, &Z, &X);
        V[2*i-1].x = X; V[2*i-0].x = X;
        V[2*i-1].y = Y; V[2*i-0].y = Z;
        V[2*i-1].z = Z; V[2*i-0].z = Y;
    }

    sort(V + 1, V + 2 * M + 1);
    memset(W, -1, sizeof(W));

    for(int i = 1; i <= 2 * M; i ++){
        X = Rad(V[i].y);
        Y = Rad(V[i].z);
        if(X != Y){
            switch(W[X] - W[Y] >= 0)
            {
                case 0:{W[Y]+=W[X];W[X]=Y;break;}
                case 1:{W[X]+=W[Y];W[Y]=X;break;}
            }
            cost += V[i].x; K ++;
            T[K][1] = V[i].y;
            T[K][2] = V[i].z;
        }
    }

    printf("%d\n%d\n", cost, K);

    for(int i = 1; i <= K; i ++)
        printf("%d %d\n", T[i][1], T[i][2]);

    return 0;
}

//wW