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

using namespace std;

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

graf G[2*NMAX], sol[NMAX];
int arb[NMAX], N, M;

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

void grup(int i, int j){
    i = arb[i];
    j = arb[j];
    for(int k = 1; k <= N; ++k)
        if(arb[k] == i)
            arb[k] = j;
}

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