#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];

inline int Rad(int nod){
    if(W[nod] <= 0) return nod;
    if(W[nod] >= 0) return Rad(W[nod]);
}

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