#include <stdio.h>
#include <algorithm>
#define NMAX 400005

using namespace std;

struct graf{
    int x, y, c;
};

bool cmp(graf a, graf b){
    return a.c < b.c;
}

graf v[NMAX], sol[NMAX];
int arb[NMAX];

int main(){
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int N, M, cost, k, i;
    scanf("%d %d", &N, &M);
    for(int i = 1; i <= M; ++i)
        scanf("%d %d %d", &v[i].x, &v[i].y, &v[i].c);
    sort(v+1, v+M+1, cmp);
    for(int i = 1; i <= N; ++i)
        arb[i] = i;
    cost = k = 0;
    i = 1;
    while(k < N-1){
        if(arb[v[i].x] != arb[v[i].y]){
            ++k;
            sol[k].x = v[i].x;
            sol[k].y = v[i].y;
            cost += v[i].c;
            for(int j = 1; j <= N; ++j)
                if(arb[j] == arb[v[i].y])
                    arb[j] = arb[v[i].x];
        }
        ++i;
    }
    printf("%d\n%d\n", cost, k);
    for(int i = 1; i <= k; ++i)
        printf("%d %d\n", sol[i].x, sol[i].y);
    return 0;
}